[Baekjoon]백준 6603번 로또

6603번 로또 문제 풀이

문제

• 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제

입력 
7 1 2 3 4 5 6 7
0

출력
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

해결방법

• next_permutation을 이용하여 다음 순열을 출력하게 되면 6개의 값만 주어졌을 때는 상관이 없으나 그 이상의 값이 주어지면 순서만 다르지 가지고 있는 인자 값들이 중복이 되는 경우가 발생한다.
  • ex> [1 2 3 4 5 6 7 ] ==> [1,2,3,4,5,6], [1,2,3,4,6,5], [1,2,3,6,5,4] 순서만 다르지 결국 가지고 있는 값들은 세 가지 모두 동일하다.

변수	내용
k	로또번호 배열
a	0,1을 저장시킬 배열
current	6가지 로또번호 조합
save	current를 저장시킬 배열

• 결과적으로 a[]를 next_permutation 시키면서 값이 1일 때 k[]에서 동일한 인덱스의 값을 가져와 current에 저장시킨 후 save에 조합을 저장시키는 방법이다.

  for (int i = 0; i < n - 6; i++) {
    a.push_back(0);
  }
  for (int i = 0; i < 6; i++) {
    a.push_back(1);
  }
  vector<vector<int>> save;
  do {
    vector<int> current;
    for (int i = 0; i < n; i++) {
        if (a[i] == 1) {
            current.push_back(k[i]);
        }
    }
    save.push_back(current);
  } while (next_permutation(a.begin(), a.end()));

• 6가지의 번호를 선택하기 때문에 '0'의 개수는 n-6 개가 되며 '1'은 6개를 넣어주게 된다.
• 주의할 점으로는 a[]에 값을 저장시킬 때 '0'부터 저장시킨 경우 실제 k[]를 통해 만들어지는 조합은 사전 순이 아닌 반대 순서로 저장되기 때문에 마지막에 꼭 sort를 사용해야 한다.
• 이게 번잡하다면 '1'부터 저장시킨 후에 prev_permutation을 사용하면 된다.

코드

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

int main() {
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;
        vector<int> a;
        vector<int> k(n);
        for (int i = 0; i < n; i++) {
            cin >> k[i];
        }
        for (int i = 0; i < n - 6; i++) {
            a.push_back(0);
        }
        for (int i = 0; i < 6; i++) {
            a.push_back(1);
        }
        vector<vector<int>> save;
        do {
            vector<int> current;
            for (int i = 0; i < n; i++) {
                if (a[i] == 1) {
                    current.push_back(k[i]);
                }
            }
            save.push_back(current);
        } while (next_permutation(a.begin(), a.end()));
        sort(save.begin(), save.end());
        for (auto x : save) {
            for (int i = 0; i < x.size(); i++) {
                cout << x[i] << ' ';
            }
            cout << '\n';
        }
        cout << '\n';
    }
    return 0;
}