[백준 6603번] 로또 - (java)

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

풀이 

이 문제는 k 개의 숫자 중에서 무조건 6개를 고르는 방법의 수를 구하는 문제이므로 모든 경우의 수를 다 확인해 봐야한다. 모든 경우의 수를 다 확인한다고 해도 k가 나올 수 있는 최대 값이 13 이므로 2^13 = 8192 번 이므로 시간내에 충분히 확인이 가능하다.

모든 경우를 다 확인해도 되지만 이 문제의 경우 백트래킹을 사용해도 된다. (상태 공간 트리를 생각하면 쉽게 아이디어가 떠오른다.)

답을 출력할때 오름차순으로 출력을 해야된다는 조건이 있으므로 항상 해당 인덱스의 값을 추가하는것을 먼저 한다. 

 

코드 

package baekjoon;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> lotto = new ArrayList<>(); // 정답을 담을 전역 변수
    static int len;

    private static void bt(int[] arr,int idx, int cnt){
        if(cnt==6) {
            for(int num : lotto){
                System.out.print(num+ " "); // 6개 다 선택되면 바로 출력
            }
            System.out.println();
            return; // 더이상 진행 X
        }

        if(idx==len) return; // 마지막 index에 있는 번호까지 확인을 했을 경우 더이상 진행 X

        lotto.add(arr[idx]); // 선택한 로또 번호 추가
        bt(arr,idx+1,cnt+1);
        lotto.remove(lotto.size()-1); // 하나 삭제
        bt(arr,idx+1,cnt);


    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(true){
            int k = sc.nextInt();
            if(k==0) break; // Test case 종료 조건
            int[] arr = new int[k];

            for(int i = 0; i<k; i++){
                arr[i] = sc.nextInt();
            }
            len = arr.length;
            bt(arr,0,0);
            System.out.println();

        }



    }
}