[백준 6603] 로또 (java)

[백준 6603] 로또 (java)

문제 출처 : 링크

입력 받은 수 중에서 나올 수 있는 로또의 결과를 모두 출력해야 하는 문제다.

이 문제는 DFS 백트래킹을 이용해서 많이 푼다고 하는데, 12개의 숫자 중에 6개를 고르는 것이므로 조합을 이용해도 충분히 결과를 구할 수 있을 것 같아서 조합을 이용했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main6603 {
 
    static int[] map;
    static int[] set;
    static int N;
    static int K = 6;
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        boolean chk = true;
        
        while(chk){
            
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            N = Integer.parseInt(st.nextToken());
            
            if(N == 0) { // 0 들어오면 나가기
                chk = false;
                break;
            }
            
            map = new int[N];
            set = new int[10000000];
            
            for (int i = 0; i < N; i++) {
                map[i] = Integer.parseInt(st.nextToken());
            }
            
            comb(set, 0, N, K, 0);
            System.out.println();
        }
    }
    
    public static void comb(int[] set, int size, int N, int K, int index){
        
        if(K==0){
            for (int i = 0; i < size; i++) {
                System.out.print(map[set[i]] + " ");
            }
            System.out.println();
            return;
        }
        if(index==N) return;
        
        set[size] = index;
        comb(set, size+1, N, K-1, index+1);
        comb(set, size, N, K, index+1);
    }
 
}