[6603번] 로또

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

6603번: 로또

이번 로또 문제는 주어진 k개의 수들 중에 6개의 수를 골라서 출력하는 문제입니다.

 

k가 8이라고 했을 때 k개 중에 6개를 고른다는 것은 k개 중에 2개를 고르는 것과 같습니다.

골랐다는 의미를 1이라고 하고, 고르지 않았음을 0이라고 했을 때,

골라야 하는 수의 개수는 6개이므로 고르지 않은 수는 k-6개입니다.

새로운 순열을 하나 만드는데, 0을 k-6개, 1을 6개 넣은 배열을 만듭니다.

이 수열을 next_permutation하면서 다음 순열을 구해나가면 1이 배치되는 번째의 수가 당첨된 수가 됩니다.

 

수열 안에 같은 수가 존재하더라도 next_permutation은 중복되는 순열이 없이 모든 조합을 구할 수 있습니다. 

 

단순히 1인 자리의 수들을 출력하게 되면 내림차순으로 출력이 됩니다.

이는 00111111이 처음 순열로 시작되기 때문인데요.

이를 오름차순으로 출력하기 위해 위와 같이 만들어지는 수열을 저장한 후, 그 수열들을 저장한 전체 배열을 다시 한번 오름차순 정렬해주어야 하는 과정을 거쳐야 합니다.

 

[코드1]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
    int k;
    while(cin >> k) {
        if (k == 0) break;
        vector<int> arr(k);
        for (int i = 0; i < k; i++) {
            cin >> arr[i];
        }
        vector<int> t;
        for (int i = 0; i < k - 6; i++) {
            t.push_back(0); //로또가 당첨되지 않을 자리는 0
        }
        for (int i = 0; i < 6; i++) {
            t.push_back(1); //로또가 당첨될 자리는 1
        }
        vector<vector<int>> ans;
        do {
            vector<int> now;
            for (int i = 0; i < k; i++) {
                if (t[i] == 1) { //1인 자리의 수가 당첨된 것이므로 그 수를 now에 저장
                    now.push_back(arr[i]);
                } 
            }
            ans.push_back(now);
        }while (next_permutation(t.begin(), t.end()));
        //오름차순으로 정렬
        sort(ans.begin(), ans.end());
        //출력
        for (auto &v : ans) {
            for (int i = 0; i < v.size(); i++) {
                cout << v[i] << ' ';
            }
            cout << '\n';
        }
        cout << '\n';
    }
    return 0;
}

[결과]

7 1 2 3 4 5 6 7 
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 

8 1 2 3 4 5 6 7 8
1 2 3 4 5 6 
1 2 3 4 5 7 
1 2 3 4 5 8 
1 2 3 4 6 7 
1 2 3 4 6 8 
1 2 3 4 7 8 
1 2 3 5 6 7 
1 2 3 5 6 8 
1 2 3 5 7 8 
1 2 3 6 7 8 
1 2 4 5 6 7 
1 2 4 5 6 8 
1 2 4 5 7 8 
1 2 4 6 7 8 
1 2 5 6 7 8 
1 3 4 5 6 7 
1 3 4 5 6 8 
1 3 4 5 7 8 
1 3 4 6 7 8 
1 3 5 6 7 8 
1 4 5 6 7 8 
2 3 4 5 6 7 
2 3 4 5 6 8 
2 3 4 5 7 8 
2 3 4 6 7 8 
2 3 5 6 7 8 
2 4 5 6 7 8 
3 4 5 6 7 8 

0

 

 

 

[코드2]

코드1에서 출력 부분 문제 때문에 2차원 배열을 이용했었는데요.

좀 더 단순하게 출력하도록 수정해보겠습니다.

이번에는 d 배열을 만들 때, 1을 먼저 6개 넣고 나머지에 0을 넣어서 마지막 순열을 만들어놓습니다.

그래야 입력으로 주어진 a 배열은 무조건 오름차순으로 주어지기 때문에 앞쪽의 작은 수부터 먼저 뽑혀야 출력 시 오름차순으로 제대로 출력이 되기 때문이에요. 그리고 순열을 만들 때는 거꾸로 prev_permutation으로 이전 순열을 하나씩 구해나가면서 바로 출력을 하면 됩니다.

아래 코드 역시 동일한 결과가 출력됩니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
    while (true) {
        int k;
        cin >> k;
        if (k == 0) break;
        vector<int> a(k);
        for (int i = 0; i < k; i++) {
            cin >> a[i];
        }
        vector<int> d;
        //1을 먼저 넣고 0을 넣으면 마지막 순열이 됨
        for (int i = 0; i < 6; i++) {
            d.push_back(1);
        }
        for (int i = 0; i < k - 6; i++) {
            d.push_back(0);
        }
        do {
            for (int i = 0; i < k; i++) {
                if (d[i] == 1)
                    cout << a[i] << ' ';
            }
            cout << '\n';
        } while(prev_permutation(d.begin(), d.end())); //이전순열
        cout << '\n';
    }
    return 0;
}

[결과]

7 1 2 3 4 5 6 7 
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 

8 1 2 3 4 5 6 7 8
1 2 3 4 5 6 
1 2 3 4 5 7 
1 2 3 4 5 8 
1 2 3 4 6 7 
1 2 3 4 6 8 
1 2 3 4 7 8 
1 2 3 5 6 7 
1 2 3 5 6 8 
1 2 3 5 7 8 
1 2 3 6 7 8 
1 2 4 5 6 7 
1 2 4 5 6 8 
1 2 4 5 7 8 
1 2 4 6 7 8 
1 2 5 6 7 8 
1 3 4 5 6 7 
1 3 4 5 6 8 
1 3 4 5 7 8 
1 3 4 6 7 8 
1 3 5 6 7 8 
1 4 5 6 7 8 
2 3 4 5 6 7 
2 3 4 5 6 8 
2 3 4 5 7 8 
2 3 4 6 7 8 
2 3 5 6 7 8 
2 4 5 6 7 8 
3 4 5 6 7 8 

0