백준 6603 로또

이 문제는 배열 안에 중복된 수가 있어도 next_permutation이 잘 작동한다는 것을 이용해서 푼다.

 

예시와 같이 k=8, s={1,2,3,5,8,13,21,34}인 경우 0을 먼저 6개 넣고, 다음에 1을 2개 넣어야 한다.

그렇게 되면 0 0 0 0 0 0 1 1과 같은 vector가 만들어지고, 이를 next_permutation을 사용해 섞으면 뒤에서 부터 섞이게 되어 모든 순열을 다 검사할 수 있다.

만약 1을 6개 먼저 넣고 0을 2개 넣게 되면, 1 1 1 1 1 1 0 0 과 같은 vector가 만들어지고, 모든 순열을 다 검사하지 못하게 된다.

원소는 오름차순으로 입력받기 때문에 sorting할 필요가 없다.

 

0과 1을 vector에 넣을 때 조심해야 한다.

vector<int> v(n)과 같이 선언할 경우 n개의 공간이 이미 만들어지기 때문에 v.push_back으로 원소를 넣을 경우 n+1번 째부터 값이 들어간다. v[n-1]에 값을 넣고 싶은 경우 v[n-1] = 1; 이렇게 넣어야 된다는 말이다.

v.push_back(1)로 넣으면 v[n]의 값이 1이 된다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
 
int main(int argc, char** argv) {
    int k;
    int s[13];
 
    while (1) {
        cin >> k;
        if (k == 0)break;
 
        vector<int> s(k);
        for (int i = 0; i < k; i++)cin >> s[i];
 
        vector<int>v(k);
        for (int i = 0; i < 6; i++)v[i] = 0;//처음 6개의 수를 0으로 넣는다.
        for (int i = 6; i < k; i++)v[i] = 1;//나머지 수를 1로 넣는다.
 
        do {
            for (int i = 0; i < k; i++) {
                if (v[i] == 0)printf("%d ", s[i]);
            }
            printf("\n");
        } while (next_permutation(v.begin(), v.end()));
        printf("\n");
    }
 
    return 0;
}