❌6603-로또

• 1~49 중 숫자 6개를 고름

• 로또 번호 선택하는 전략 중 49개 숫자에서 k(k>6)개의 숫자를 골라 집합 S를 만듬

• 그 집합 S만 가지고 번호 선택

k=8, S={1,2,3,5,8,13,21,34}일 때

• 1,2,3,5,8,13

• 1,2,3,5,8,21

이런식으로 오름차순으로 된 모든 집합 S를 출력하라

남이 푼거

선택할 수 있는 모든 경우의 수를 오름차순으로 출력하면 된다. 일단 선택할 수 있는 모든 경우의 수에서 브루트포스라는 것을 알 수 있다.

S에서 각 원소를 시작점으로 하여 dfs를 수행하면 모든 경우의 수를 구할 수 있음

• dfs는 현재 정점에서 이동할 수 있는 정점을 인접행렬 혹은 인접리스트로 하는데

  • 여기서는 그냥 현재 인덱스보다 큰 인덱스로 이동하면된다.

  • 그래서 visited가 필요없다. 방문했던 인덱스를 또 방문할 일이 없기 때문이다.

int size, numList[49];
int visited[49];
vector <int> visitedPath;
const int PICK_NUM = 6;

void dfs(int start, int count) {
    if(count >= 6) {
        for(int i = 0; i<count; i++) {
            cout<<visitedPath[i]<<" ";
        }
        cout<<endl;
        return;
    } else {
        for(int i = start + 1; i<size; i++) {
            if(!visited[i]) {
//                visited[i] = true;
                visitedPath.push_back(numList[i]);
                count += 1;
                dfs(i, count);
                visitedPath.pop_back();
                count -= 1;
            }
        }
    }
//    for(int i = start + 1; i < size; i+=1) {
//        visited[i] = false;
//    }
}

int main() {
    cin>>size;
    for(int i = 0; i<size; i+=1) {
        cin>>numList[i];
    }

    while(size != 0) {
        for(int i = 0; i<=size-PICK_NUM; i+=1) {
            visitedPath.push_back(numList[i]);
            dfs(i, 1);
            visitedPath.pop_back();
        }
        cout<<endl;
        cin>>size;
        for(int i = 0; i<size; i+=1) {
            cin>>numList[i];
        }
    }

    return 0;
}