[BOJ] 6603. 로또

로또

클릭시 이동합니다.

어떻게 풀까?

조합 문제입니다!

심지어 숫자들도 오름차순으로 들어오기 때문에, 조합 짜는 코드만 잘 짜주시면 됩니다!

참고로, 최대 길이가 13밖에 되지 않으니, 선택했다는 것을 비트로 이용하여 나타낼 수 있습니다!

재귀 함수로 순열을 짜는 방법은 다음과 같습니다.

1. 해당 배열을 선택한다!

 - 이 경우에는 해당 배열을 선택했다는 select check를 해주고 다음 인덱스를 확인합니다.

2. 해당 배열을 선택하지 않는다!

 - 이 경우에는 아무런 처리를 하지 않고 다음 인덱스를 확인합니다!

이렇게 하면, 마지막에 r이 0이 되거나, n이 r과 같아지는 경우에는 visit을 적절하게 1로 만들면서 

visit을 이용하여 선택된 숫자들을 출력하면 됩니다.

코드

//https://www.acmicpc.net/problem/6603
//로또
#pragma once
#include<cstdio>
#include<iostream>
 
using namespace std;
 
int nums[13];
int k;
void func(int visit) {
    int idx = 0;
    while(visit)
    {
        if (visit & 1) {
            printf("%d ", nums[idx]);
        }
        idx++;
        visit >>= 1;
    }
    printf("\n");
}
void celcious(int depth,int selected, int visit) {
    if (k - depth == 6 - selected || selected == 6)
    {
        for (int i = 0; i < 6 - selected; i++) {
            visit |= 1 << (depth + i);
        }
        func(visit);
        return;
    }
 
    celcious(depth + 1, selected + 1, visit | (1 << depth));
    celcious(depth + 1, selected, visit);
}
 
int BOJ6603() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    while (true)
    {
        cin >> k;
        if (k == 0) break;
        for (int i = 0; i < k; i++) {
            cin >> nums[i];
        }
        celcious(0, 0, 0);
        printf("\n");
    }
    return 0;
}

시간 복잡도

의 시간 복잡도가 걸립니다!

따라서, 시간 복잡도는 O(N!) 입니닷