로또 6603번 - 순열

로또 6603번 (완전탐색-순열)

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

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	128MB	4821	2685	1995	55.602%

algorithm에 있는 순열함수인 next_permutation을 이용하여

만약 7개 중에 6개를 골라야한다면, 배열에 0을 1개 , 1을 6개 넣어서 나올수 있는 모든 순열을 쫘르르륵 한다음에 1이 위치하고있는 인덱스를 활용하면, 7가지 숫자중 6개의 모든 조합을 추출할 수 있다. 말로는 이해하기 어려울수 있으니 소스를 참고바람.

 

문제

독일 로또는 {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이 하나 주어진다.

출력

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

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

예제 입력

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

예제 출력

 
xxxxxxxxxx
​
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

 

소스코드

 
xxxxxxxxxx
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int k;
    while (cin >> k)
    {
        if (k == 0) break;
        vector<int> v(k);
        for (int i = 0; i < k; i++)
            cin >> v[i];
​
        vector<int> d(k);
        for (int i = 0; i < k - 6; i++)
            d[i] = 0;
        
        for (int i = k - 6; i < k; i++)
            d[i] = 1;
        
        vector<vector<int>> ans;
        do {
            vector<int> current;
            for (int i = 0; i < k; i++)
            {
                if (d[i] == 1)
                    current.push_back(v[i]);
            }
            ans.push_back(current);
        } while (next_permutation(d.begin(), d.end()));
​
        sort(ans.begin(), ans.end());
        
        for (int i = 0; i < ans.size(); i++)
        {
            for (int j = 0; j < ans[i].size(); j++)
                cout << ans[i][j] << ' ';
            cout << '\n';
        }
        cout << '\n';
    }
    return 0;
}