[백준 / C++] 로또 (실버2, 6603)

문제

독일 로또는 {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

---

문제 풀이

이번 문제는 N개의 집합에서 6개를 중복 없이 뽑는 조합을 구하는 간단한 문제입니다.

 

조합은 재귀방식과 중첩 for문 형식으로 구현이 가능하나 뽑는 개수가 3개 미만일 때만 중첩 for문을 사용하는 것이 좋으며, 그렇기에 이번 문제에서는 재귀 방식으로 조합을 구현하게 되었습니다.

 

전체적인 로직을 간단히 설명한다면 다음과 같습니다.

1. 숫자를 저장할 벡터 컨테이너 생성 (nums)

2. 현재 들어간 수(cnt) + 1부터 전체 숫자를 순회하며 벡터 컨테이너(nums)에 값 저장 후 재귀

3. 특정 조건(nums의 사이즈가 6)을 만족하면 반환

4. 반환되면 벡터 컨테이너(nums) 에서 현재 값 제거 (pop_back())

 

조합을 만드는 방식은 그리 어려운 로직은 아니라고 생각되며, 완전 탐색 중 특정 조건에 가지를 치는 백트래킹 알고리즘에 속하니 확실히 암기하고 넘어가도 좋을 것 같습니다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> v;

void Go(int cnt, vector<int>& nums)
{
    if (nums.size() == 6)
    {
        for (int num : nums)
        {
            cout << v[num] << " ";
        }
        cout << endl;
        return;
    }

    for (int i = cnt; i < n; i++)
    {
        // 컨테이너에 값 추가
        nums.push_back(i);
        
        // 재귀 호출
        Go(i + 1, nums);
        
        // 추가된 값 제거
        nums.pop_back();
    }
}

int main()
{
    while (true)
    {
        cin >> n;

        if (n == 0) break;

        for (int i = 0; i < n; i++)
        {
            int temp = 0;
            cin >> temp;

            v.push_back(temp);
        }

        vector<int> temp;
        Go(0, temp);


        v.clear();
        cout << '\n';
    }
}