[BOJ] 6603 - 로또 JAVA

www.acmicpc.net/problem/6603

6603번: 로또

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력 1

7 1 2 3 4 5 6 7

8 1 2 3 5 8 13 21 34 0

예제 출력 1

1 2 3 4 5 6

1 2 3 4 5 7

1 2 3 4 6 7

1 2 3 5 6 7

1 2 4 5 6 7

1 3 4 5 6 7

2 3 4 5 6 7

 

1 2 3 5 8 13

1 2 3 5 8 21

1 2 3 5 8 34

1 2 3 5 13 21

1 2 3 5 13 34

1 2 3 5 21 34

1 2 3 8 13 21

1 2 3 8 13 34

1 2 3 8 21 34

1 2 3 13 21 34

1 2 5 8 13 21

1 2 5 8 13 34

1 2 5 8 21 34

1 2 5 13 21 34

1 2 8 13 21 34

1 3 5 8 13 21

1 3 5 8 13 34

1 3 5 8 21 34

1 3 5 13 21 34

1 3 8 13 21 34

1 5 8 13 21 34

2 3 5 8 13 21

2 3 5 8 13 34

2 3 5 8 21 34

2 3 5 13 21 34

2 3 8 13 21 34

2 5 8 13 21 34

3 5 8 13 21 34

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;

    static int K;
    static int[] S = null;
    static int[] lotto = null;
    static boolean[] check = null;

    public static void dfs(int dept) {
        if(dept == 6) {
            for(int i = 0; i < 6; i++) {
                sb.append(lotto[i] + " ");
            }
            sb.append("\n");
            return;
        }

        for(int i = 0; i < K; i++) {
            if(!check[i] && S[i] > lotto[dept - 1]) {
                lotto[dept] = S[i];
                check[i] = true;
                dfs(dept + 1);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        while(true) {
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());

            if(K == 0) break;

            S = new int[K];
            lotto = new int[6];
            check = new boolean[K];
            for(int i = 0; i < K; i++) {
                S[i] = Integer.parseInt(st.nextToken());
            }

            for(int i = 0; i < K; i++) {
                lotto[0] = S[i];
                check[i] = true;
                dfs(1);
                check[i] = false;
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

백트래킹을 통해 가능한 모든 조합을 만들어 낸다.

 

주의할 점은, 오름차순 조합에 대해서만 출력하는 것이다.

즉, 같은 숫자들로 만들어진 조합이라도 오름차순일 때만 정답으로 친다.

ex ) 1, 2, 3, 4, 5, 6 으로 만들어진 여러 조합들 (1, 2, 3, 4, 5, 6), ... , (6, 5, 4, 3, 2, 1) 중에서는 (1, 2, 3, 4, 5, 6) 하나만 정답으로 친다는 것.

 

이를 위해 현재 lotto[]의 마지막 원소보다 값이 큰 경우에만 재귀를 하도록 하는 조건을 추가했다.

 

이렇게하면 오름차순이 유지되지 않는 조합은 만드는 것을 중단하기 때문에 모든 조합을 만들어놓고 오름차순 여부를 검사하는 것보다 더 빠르게 실행할 수 있다.

 

사실 이것보다 더 효율적인 방법이 있긴 하다.

 

사전에 S[]를 미리 오름차순 정렬해놓고,

이전에 입력받은 숫자의 S[] 에서의 인덱스를 기억하며 그 인덱스보다 큰 인덱스를 갖는 S[]의 원소만 재귀하도록 하는 것이다.

    public static void dfs(int idx, int dept) {
        if(dept == 6) {
            for(int i = 0; i < 6; i++) {
                sb.append(lotto[i] + " ");
            }
            sb.append("\n");
            return;
        }

        for(int i = idx; i < K; i++) {
            if(!check[i]) {
                lotto[dept] = S[i];
                check[i] = true;
                dfs(i + 1, dept + 1);
                check[i] = false;
            }
        }
    }

 

이렇게 하면 헛도는 반복마저도 하지 않게 될 수 있으니 더 빨리 처리할 수 있게 된다.

(사실 그렇게 큰 차이는 아닌 듯 하다.)

 

 

그렇게 큰 차이도 아니고 코드를 이해하기가 더 쉬운 위유로 첫번째 방법이 더 나은 듯 하다.