백준 6603번 - 로또

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

이 문제는 다양한 방법으로 해결할 수 있다.
내가 접근한 문제 해결 방법은 dfs와 다음 순열을 이용하는 방법이다.


#1

dfs의 경우 
0부터 n까지 깊이 탐색을 하는 것인데, 
해당 인덱스의 숫자를 고를지 말지를 visited 변수를 통해 각각 1과 0으로 체크했다. 
만약에 체크한 개수가 6개일 때는 체크된 인덱스를 출력해주고 리턴하면 된다.


계속해서 체크되지 않는 경우에는
남아있는 번호 개수보다 체크해야 할 개수가 많을 때 백트래킹 하여 검사하지 않도록 했다.


예를 들어 10개 중에 7번째까지 2개를 체크했을 때
나머지 8,9,10을 모두 체크한다고 하더라도 총 5개를 체크하면 6개가 되지 않기 때문에 
이를 검사할 필요는 없다.

#include <iostream>
#include <vector>
using namespace std;
 
int n;
vector<int> arr;
vector<int> visited;
 
void dfs(int step,int cnt){
    
    if(cnt==6){
        for(int i=0;i<n;i++)
            if(visited[i])
                printf("%d ",arr[i]);
        
        printf("\n");
        return;
    }
    
    //남은 원소 모두 선택해도 6개 안될 때
    if(n-step<6-cnt)
        return;
    
    visited[step]++;
    dfs(step+1,cnt+1);
    
    visited[step]--;
    dfs(step+1,cnt);
    
}
int main(){
    
    
    while(true){
        scanf("%d",&n);
        if(n==0)
            break;
        
        arr=vector<int> (n,0);
        visited=vector<int> (n,0);
        
        for(int i=0;i<n;i++)
            scanf("%d",&arr[i]);
        
        
        dfs(0,0);
        printf("\n");
    }
    return 0;
}

#2

다음 순열에서 총 n 개의 원소가 있을 때 
앞에 있는 6개의 원소를 0으로 체크하고 나머지를 1로 체크하여 문제를 해결하였다.


예를 들어 원소의 개수가 7개 있다고 가정한다면

0번째 원소부터 6번째 원소까지
"0,0,0,0,0,0,1"이 있다. 이때 0이 있는 인덱스의 원소를 출력해준다.

다음으로 
"0,0,0,0,0,1,0"이 있을 때 0이 있는 인덱스의 원소를 출력해주면 된다.
그리고 이를 반복해주면 된다.


처음에 원소가 오름차순으로 정렬되어 있기 때문에 sort를 할 필요는 없고
다음 순열을 이용하여 원소가 작은 순서대로 출력해주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main(){
    
    int n;
    
    while(true){
        scanf("%d",&n);
        
        if(n==0)
            break;
        
        vector<int> arr(n,0);
        vector<int> vec(n,0);
        for(int i=0;i<n;i++)
            scanf("%d",&arr[i]);
        
        for(int i=6;i<n;i++)
            vec[i]=1;
        
        do{
            for(int i=0;i<n;i++)
                if(vec[i]==0)
                    printf("%d ",arr[i]);
            
            printf("\n");
        }while(next_permutation(vec.begin(),vec.end()));
        
        printf("\n");
        
    }
    
    return 0;
}