백준 6603 - 로또

문제

 

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

6603번: 로또

 

 

풀이

 

집합 S에 저장된 숫자들에 대해서 6개를 선택해서 만들 수 있는 조합을 출력하는 문제이다.

 

순열을 이용해서 조합을 구할 때는, 몇 개를 선택해서 조합을 이룰건지 알아야 한다. 이 때, 선택한 수들은 같은 숫자로 바꾸고 그 외 숫자들도 같은 수로 바꿔서 순열을 구하면 조합을 구할 수 있다.

 

예를 들어, 1 2 3 4 에서 3개를 선택해서 조합을 이루는 수를 구한다고 하면, 이 순열을 0 0 0 1로 바꾸고 0 0 0 1 에 대한 순열을 구한다. 그러면

0 0 0 1, 0 0 1 0, 0 1 0 0, 1 0 0 0 

네 가지 순열이 나오게 되고 원래 데이터에서 0이 있는 자리와 매칭되는 숫자들만 선택한다고 하면 다음과 같은 조합을 구할 수 있다.

1 2 3, 1 2 4, 1 3 4, 2 3 4 가 되고 가능한 조합은 네 개가 된다.

 

이 점을 이용해 문제를 해결한다.

 

 

코드

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int k;
int s[13];
int a[13];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    while (true)
    {
        cin >> k;
        if (!k) break;
        for (int i=0; i<k; i++)
            cin >> s[i];
        for (int i=6; i<k; i++)
            a[i] = 1;
 
        do
        {
            for (int i=0; i<k; i++)
            {
                if (a[i]) continue;
                cout << s[i] << ' ';
            }
            cout << '\n';
        } while (next_permutation(a, a+k));
        cout << '\n';
    }
 
    return 0;
}