[BOJ - 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>

간단하게 재귀를 통해서 구현하면 된다.

6개의 값을 담을 combination 배열을 선언하고 재귀로 현재 index와 개수, 그리고 배열을 재귀로 넘겨준 후 cnt가 6일 경우에 배열에 있는 값들을 출력하면 된다.

처음에는 나도 visited를 통해서 구현을 하였는데 따로 방문값 저장 필요 없이 배열을 들고다니면서 출력을 하는 게 효율적이다.

 

<방식2>

주어진 배열에서 6개를 뽑는 문제인데 순열로 취급하여 next_permutation, prev_permutation을 이용하면 간단하게 풀 수 있다.

순열과 조합의 차이는 n개를 뽑을 때 순서에 따라 다른 값으로 취급하면 순열, 순서를 상관하지 않고 뽑는다면 조합이다.

코드에서는 prev_permutation을 사용하는데 처음에 selected[i]에 1을 넣기 때문에 1111110000000로 시작한다.

따라서 next_permutation을 쓰면 다음 숫자가 없는데 prev_permutation을 통해서 1111101000000으로 순서대로 뽑는 것이다.

실제 배열은 123456 123457이지만 selected 배열은 반대로 간다고 생각하면 된다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int lotto[13], n;

void generate_combinations(int idx, int cnt, int combination[]) {
    if (cnt == 6) {
        for (int i = 0; i < 6; i++) {
            cout << combination[i] << " ";
        }
        cout << "\n";
        return;
    }
    for (int i = idx; i < n; i++) {
        combination[cnt] = lotto[i];
        generate_combinations(i + 1, cnt + 1, combination);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

        for (int i = 0; i < n; i++) {
            cin >> lotto[i];
        }
        sort(lotto, lotto + n);

        int combination[6]; // 현재 조합을 저장할 배열
        generate_combinations(0, 0, combination);
        cout << "\n";
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

        int lotto[13];
        for (int i = 0; i < n; i++) {
            cin >> lotto[i];
        }
        sort(lotto, lotto + n); 

        int selected[13] = { 0 };
        for (int i = 0; i < 6; i++) {
            selected[i] = 1; 
        }

        do {
            for (int i = 0; i < n; i++) {
                if (selected[i]) {
                    cout << lotto[i] << " ";
                }
            }
            cout << "\n";
        } while (prev_permutation(selected, selected + n));

        cout << "\n";
    }
    return 0;
}