백준 6603 로또

백준 6603 로또

1. 문제 링크

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

6603번: 로또

2. 풀이

1. 이 문제는 조합의 대표 유형이다.
2. 조합은 순서를 고려하지 않기 때문에 아래의 경우는 1개로 카운트 한다.
3. - [1, 2, 3] / [1, 3, 2] / [2, 1, 3]
4. [1, 2, 3] 에서 2개를 뽑는 경우를 생각해본다.
5. 가능한 경우는 [1, 2] / [1, 3] / [2, 3] 총 3개이다.
6. 처음 1을 뽑고 나서 1이 포함된 모든 경우를 구한 뒤부터는 1은 나오지 않는다.
7. 따라서 getLotto에서 재귀 호출 시 i + 1을 하여 다음 depth에서 이전 depth에서 고려된 수는 제외하도록 했다.

 

3. 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            if (n == 0)
                break;
            int[] numbers = new int[line.length - 1];
            boolean[] visit = new boolean[line.length - 1];

            for (int i = 1; i <= n; i++) {
                numbers[i - 1] = Integer.parseInt(line[i]);
            }

            getLotto(0, 0, numbers, visit);

            System.out.println();
        }
    }

    static void getLotto(int depth, int index, int[] numbers, boolean[] visit) {
        if (depth == 6) {
            for (int i = 0; i < visit.length; i++) {
                if (visit[i]) {
                    System.out.print(numbers[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        for (int i = index; i < numbers.length; i++) {
            if (!visit[i]) {
                visit[i] = true;
                // 중복을 피하기 위해, 다음 depth 에서 이전의 수를 고려하지 않도록 i + 1번째부터 시작하도록 한다.
                getLotto(depth + 1, i + 1, numbers, visit);
                visit[i] = false;
            }
        }
    }
}

4. 채점 결과

5. 느낀 점

1. 조합의 전형적인 문제였으며, 익숙해져야하는 유형이다.
2. 재귀를 들어갔다 나오면서 visit 배열을 원래 상태로 만들어야한다.