백준:6603번 로또

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

6603번: 로또

 

이 문제를 순열로 풀었는데 여기서 궁금했던게 해결이 되었다. next_permuation이라는 순열 함수를 쓸 때

1,1,2,2,2 와 같이 같은 수가 있을 떄 어떻게 작동되는가인데 올바르게 작동 되는 것이다.

1 1 2 2 2

1 2 1 2 2

등등

처럼 순서대로 간다.

그래서 이 문제를 풀 때 비교배열 n개의 수에서 6개만 1을 넣고 나머지 0을 넣었다. 그리고  비교배열에 1이 들었을 떄만 그 위치 값 그대로 로또 배열에 넣어 원소가 6개인 배열을 만들었다. 이 행동을 순열 함수를 사용해서 계속한다..

말로는 이해하기 어려울 수 있으니 코드를 보자.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    while(1){
        int n;
        cin >>n; 
        if(n==0){            //탈출
            break;
        }
        vector<int> a(n);      
        for(int i=0;i<n;i++){           //집합 수
            cin>>a[i];
        }
        vector<int> d;
        for(int i=0;i<n-6;i++){        //0과 1(6개)을 넣어 순열 함수를 사용한다음 그 위치 값 그대로 원소 6개 집합 만들기
            d.push_back(0);
        }
        for(int i=0;i<6;i++){
            d.push_back(1);
        }
        vector<vector<int>> ans;
        do{
            vector<int> cur;
            for(int i=0;i<n;i++){
                if(d[i]==1){                     //1일때 위치값을 집합배열 그대로 넣기
                    cur.push_back(a[i]);
                }
            }
            ans.push_back(cur);
        }while(next_permutation(d.begin(),d.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;
}