[C++] 백준 6603: 로또

문제 이해

- 1 ~ 49 사이의 수 중에서 k개를 골라 집합 S를 만든 후 S의 부분집합의 크기가 6인 집합의 경우의 수를 모두 구하라.

 

<조건>

- 시간 제한: 1초

- 메모리 제한: 128MB

 

<입력>

- 여러 개의 테스트 케이스

- k: 수의 개수 (6 ~ 13)

※ 0이 주어지면 종료된다.

- k의 원소들 (1 ~ 49)

 

<출력>

- 수를 고르는 모든 방법을 사전순으로 출력한다.

- 각 테스트케이스 사이에는 공백을 출력하라.

 

 

---

문제 풀이

k의 원소들이 주어지면 그 중 6개를 고르는 문제이다.

백트래킹으로 쉽게 풀 수 있었는데

여기서 주의할 점은 사전순으로 출력한다는 것이다.

 

사전순으로 출력하려면 다음 원소를 선택할 때는 이전 원소보다는 다음 인덱스에 있는 것을 선택해야 한다.

이 점을 유의해서 재귀 함수의 매개변수를 깊이뿐만 아니라 인덱스도 넘겨주어야 한다.

void dfs(int depth, int idx)

 

 

또한 여러 개의 테스트 케이스가 주어지므로

한 테스트 케이스가 끝난 후, 배열의 초기화를 반드시 잘 해주자.

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

int k;
int arr[20];
bool visited[20];
vector <int> ans;

void dfs(int depth, int idx){
    if(depth == 6){
        for(int i = 0 ; i < 6; i++){
            cout<<ans[i]<<" ";
        }
        cout<<"\n";
    }

    for(int i = idx; i < k; i++){
        if(!visited[i]){
            visited[i] = true;
            ans.push_back(arr[i]);
            dfs(depth+1, i+1);
            ans.pop_back();
            visited[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while(true){
        cin>>k;
        if(k == 0) break;

        ans.clear();
        for(int i = 0; i < k; i++) visited[i] = false;

        for(int i = 0; i < k; i++){
            cin>>arr[i];
        }

        dfs(0, 0);
        cout<<"\n";
    }
    return 0;
}