백준 로또 6603

1. 로또6603

2. 컴퓨팅 스킬

• vector check 변수에 6개를 뽑는 경우의 수 이므로, k-6개만큼은 0을 푸쉬백 해주고, 6개까지에 1을 넣어줍니다.
• check배열로 next_permutation을 수행합니다. true인경우가 조합을 구하는 경우의 수입니다.
• 테스트케이스를 돌면서 vectorv, vector check의 값의 초기화값을 잘 생각해주어야한다. 초기화가 원활하게 이루어지지않을 경우 이상한 값을 가득담고있습니다.
  값이 들어있는 vector<int> v; 변수를 next_permutation을 하는것이 아니라 check변수를 수행하는것입니다.

3. 컴퓨팅 사고

• 처음에 check배열을 선언해서 단순히 1의 값만넣어서 체크하였지만, check[i]==1 의 경우만 체크해주었다. 하지만, 조합이 나오는것이 아니라 순열의 값이 나오게 되어 올바르지 않은 값이다. 그 이유는 단순히 check배열을 사용하여 true,false값을 사용할 경우에는 중복된 값을 체크 할 수가 없다. check된 값을 next_permutation을 돌려주어야지 조합의 경우를 찾을 수 있습니다.
• 순열과 조합중에 조합 중복을 제거해야합니다.
• push_back 을 0 과 1을 해주는 경우를 잘 생각해야합니다. 6개를 뽑는 경우의 수 이므로, k-6개만큼은 0을 푸쉬백 해주고, 6개까지에 1을 넣어줍니다.
• 가장 중요한점은 왜 0 111111이 들어가는데 어떻게 이것을 조합을 뽑을지에 대한 고민을 했다. 단순히 0,1과으로 조합의 경우를 세어준것입니다. 순열의 경우에는 이전에 보았던 값들도 확인해주어야하지만, 조합의 경우는 이전의 값을 확인하지 않는다는것이다.
• next_permutation을 돌리게 되면서 그 순열의 값들은 계속해서 변경되기때문에 중복없는 값을 계속해서 체크해서 나갈 수 있다는점입니다.
• next_permuation을 돌린 후 그 값을 모두 ans 저장시켜 sort(ans.begin(), ans.end())를 통하여 값을 오름차순 정렬을 시켜줍니다.
  단순히 check배열로 true를 체크하는것이 아니라, check vector의 값으로 next_permutation을 돌려주면서 check[i]== true일 경우 N개중 K개를 고르는 경우를 구할 수 있습니다.

3.1. next_permutation풀이

//
//  07_백준_로또_6603.cpp
//  algorithm-level-up
//
//  Created by kgh on 02/12/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main(void){

    while(true){
        int n=0;
        cin >> n;
        vector<int> v(n);
        vector<int> check;
        if(n == 0){
            break;
        }
        for(int i=0; i<n; i++){
            cin >> v[i];
        }
        for(int i=0; i<n-6; i++){
            check.push_back(0);
        }
        for(int i=0; i<6; i++){
            check.push_back(1);
        }
        sort(v.begin(),v.end());
        vector<vector<int>> ans;
        do{
            vector<int> curr;
            for(int i=0; i<n; i++){
                if(check[i] == 1){
                    curr.push_back(v[i]);
                }
            }
            ans.push_back(curr);
        }while(next_permutation(check.begin(),check.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;
}

3.2. 백트래킹 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int check[13];
vector<int> ans;
void dfs(vector<int> v, int idx, int cnt){
    
    if(cnt == 6){
        sort(ans.begin(),ans.end());
        for(int i=0; i<ans.size(); i++){
        
            cout << ans[i] << ' ';
        }
        cout << '\n';
        return;
    }
    
    for(int i=idx; i<v.size(); i++){
        
        if(check[i] == true){
            continue;
        }
        check[i] = true;
        ans.push_back(v[i]);
        dfs(v,i,cnt+1);
        check[i] = false;
        ans.pop_back();
        
        
    }
    
    
    
}
int main(void){
    
    while(true){
        int n=0;
        cin >>n;
        
        if(n == 0){
            break;
        }
        
        vector<int> v(n);
        for(int i=0; i<n; i++){
            cin >> v[i];
        }
        
        dfs(v,0,0);
        cout << '\n';
        
        
    }
    return 0;
}