[백준] 6603번 C/C++ 풀이 _ 로또

 


출처 : https://www.acmicpc.net/problem/6603 

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB72914020288955.239%

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이 때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력 1 

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력 1 

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

출처

Contest University of Ulm Local Contest University of Ulm Local Contest 1996 F번

풀이

가능한 로또의 경우의 수를 모두 출력하는 문제입니다. 


0~6 의 인덱스를 가진 숫자(7개의 숫자)가 있다고 가정해보면 위와 같은 트리를 그릴 수 있습니다. 
루트 노드에 대하여 자식 노드들은 루트 노드보다 항상 큰 값을 가지는 트리를 구성하게 됩니다. 

위와 같이 서브트리에서의 루트 자식들은 항상 루트보다 작은 값을 가진 상태로 dfs 를 사용해서 갱신합니다. 
그리고 높이가 6이 되는 순간 가능한 원소들을 출력해주고 더 이상 탐색을 하지 않으면 문제가 해결됩니다. 

저는 재귀함수를 이용하여 dfs 를 구현했습니다.
one_answer 라는 벡터를 사용해서 dfs 가 시작할 때, 새로운 숫자를 넣어주고 끝날 때에는 pop_back 을 이용하여 빼주었습니다. 

이번에는 일부로 전역변수를 사용하지 않고 프로그래밍을 진행하여 파라미터가 조금 많습니다. 
더 간결하게 풀기 위해서는 전역변수를 쓰면 보기 더 깔끔합니다

http://jun-itworld.tistory.com/15 
위의 링크를 참조하면 조금 더 간결한 풀이를 확인하실 수 있습니다. 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector> 
#define SIZE 6
using namespace std;
 
void dfs(int _n, vector<int>& _num_vec, vector<int>& _one_answer, int _now_idx) {
    int answer_size = _one_answer.size();
    // 사이즈가 원하는사이즈 보다 크면 종료 
    if (answer_size > SIZE) return;
 
    // 출력하고 끝내기 
    if (answer_size == SIZE) {
        for (int ans_idx = 0; ans_idx < SIZE; ans_idx++)
            cout << _num_vec[_one_answer[ans_idx]] << " ";
        cout << "\n";
        return
    }
 
    // 다음 단계 dfs 가능한 노드들을 _one_answer에 추가해주는 구간
    for (int n_idx = _now_idx + 1; n_idx < _n; n_idx++) {
        // 만약, 6개를 채울 수 없는 위치의 인덱스를 선택하면 종료 
        if (answer_size + (_n - n_idx) < SIZE) return;
 
        _one_answer.push_back(n_idx);
        dfs(_n, _num_vec, _one_answer, n_idx);
        _one_answer.pop_back();
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    while (1) {
        int n;
        cin >> n; 
        if (n == 0break;
        
        // input
        vector<int> num_vec(n, 0);
        vector<int> one_answer;
        for (int n_idx = 0; n_idx < n; n_idx++)
            cin >> num_vec.at(n_idx);
 
        // dfs 수행
        for (int n_idx = 0; n_idx < n; n_idx++) {
            one_answer.push_back(n_idx);
            dfs(n, num_vec, one_answer, n_idx);
            one_answer.pop_back();
        }
    
        cout << "\n";
    }
    return 0
}
cs