[BOJ 길라잡이/Java] 12일차 #6603 로또

알고리즘 분류

- 수학

- 조합론

- 백트래킹

- 재귀

 

크기가 k인 집합 S가 주어졌을 때 그 중 6개를 고를 수 있는

경우의 수를 모두 출력하는 문제다.

 

머릿속으로는 kC6 경우의 수를

집합 S에서 해당 index 찾아 출력하면 되겠다~

생각했는데, 코드로 어떻게 combination을 구현하는지 몰라서 헤맸다.

 

찾아보니 재귀와 백트래킹을 사용해야 하는 문제였다.

아직 나에게는 너무나 낯선 백트래킹 구현...

머리로는 알겠는데 코드로 구현하는게 쉽지 않은 것 같다.

 

import java.util.*;
import java.io.*;

class Main {
    static int k;
    static int[] S, numbers;
    static StringBuilder sb;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());
            if (k == 0) {
                break;
            }
            S = new int[k];
            numbers = new int[6];
            
            for (int i = 0; i < k; i++) {
                S[i] = Integer.parseInt(st.nextToken());
            }

            combi(0, 0);
            sb.append("\n");
        }

        System.out.println(sb);
        
    }

    public static void combi(int depth, int start) {
        if (depth == 6) {
            for (int i = 0; i < 6; i++) {
                sb.append(numbers[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = start; i < k; i++) {
            numbers[depth] = S[i]; // 현재 depth(위치)에 숫자 저장
            combi(depth + 1, i + 1); // 다음 자리로 이동, 중복 방지를 위해 i+1부터 시작
        }
    }
}

 

combi(0, 0)으로 조합 생성을 시작한다.

depth = 0: 현재까지 고른 숫자 수

start = 0: 시작 인덱스

 

아직 6개가 안 골라졌다면 start부터 k까지 반복하며 숫자를 선택하고,

6개를 고르면 numbers[] 배열을 출력한다.

i+1부터 시작하므로 중복 없이 오름차순 조합이 만들어진다.