[BOJ] 6603 : 로또(Java)

문제 링크

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

6603번: 로또

---

💡 풀이

49개의 숫자 중 주어진 K개 만큼 수를 골라 그 K개 중 6개로 집합 S를 만드는 문제입니다. 

주어진 K개 중 6개를 순서 없이 중복을 허용하지 않고 고르는 경우 즉, $_kC_6$ 인 조합을 구하는 문제입니다. 조합을 구현 할 줄 안다면 간단하게 풀 수 있는 문제입니다.

조합(Combination)

자바에서 조합을 구현하기 위해 재귀를 사용했습니다. 

우선, `numbers[]` 배열은 선택한 K개의 숫자가 담긴 배열이고, `select[]` 배열은 그 중 6개를 고른 배열입니다. 

일반화해서 얘기하자면, $_nC_r$에서 n 에 해당하는 숫자 배열이 `numbers[]`, r 에서 해당하는 숫자 배열이 `select[]`라고 할 수 있습니다.

static void combination(int start, int depth) {
    // Base Case
    if (depth == 6) {
        for (int i : select) {
            sb.append(i).append(" ");
        }
        sb.append("\n");
        return;
    }

    for (int i = start; i < K; i++) {
        select[depth] = numbers[i];
        combination(i + 1, depth + 1);
    }
}

`start` 는 시작하는 숫자의 인덱스이고, `depth`는 이제까지 뽑은 숫자의 개수입니다. 

재귀가 종료되는 조건인 Base Case는 depth가 뽑고자하는 숫자의 개수인 6이 되었을 때입니다. 이때, 이제까지 저장되어 있던 `select[]` 배열에서 숫자들을 뽑아 하나의 조합을 결과에 넣어주면 됩니다. 

주의할 점은 재귀 함수 안 반복문에서 `i`의 시작점이 파라미터로 받은 `start` 라는 점입니다. 반복문의 시작점을 `start`로 잡음으로서 이전 숫자는 탐색하지 않게 되므로 중복을 피할 수 있습니다. 

 

전체 코드

전체적인 코드는 다음과 같습니다.

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

public class Q6603 {
    static int K;
    static int[] numbers;
    static int[] select;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());

            if (K == 0) break;

            sb = new StringBuilder();
            numbers = new int[K];
            for (int i = 0; i < K; i++) {
                numbers[i] = Integer.parseInt(st.nextToken());
            }
            select = new int[6];

            // kC6 구하기
            combination(0, 0);
            System.out.println(sb);
        }
    }

    static void combination(int start, int depth) {
        // Base Case
        if (depth == 6) {
            for (int i : select) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = start; i < K; i++) {
            select[depth] = numbers[i];
            combination(i + 1, depth + 1);
        }
    }
}