Backtracking 백준 알고리즘 자바 6603 ‘로또’ 문제풀이

Problem

독일 로또는 {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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

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

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

Solution

• 입력 받은 문자열의 첫번째 값은 숫자의 개수이므로 dfs를 시작할 때 1부터 시작해야 하며, 모든 루프문에서도 인덱스 1부터 시작해야 한다.
• 오름차순으로 값이 주어지므로 따로 정렬을 하지 않아도 된다.
• 총 6개의 숫자를 뽑아야 하므로 뽑은 숫자의 개수를 나타내는 d 변수가 6일 때 (0부터 시작하지만, d+1이 넘어가므로) 문자열을 처리한다.
• 이전의 백트래킹 문제와 동일하다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	static String[] line;
	static boolean[] visit;
	static int n;
	
	private static void dfs(int v, int d) throws IOException {
		if(d == 6) {
			String str = "";
			for(int i = 1; i <= n; i++) {
				if(visit[i]) str += line[i] + " ";
			}
			System.out.println(str);
			return;
		}
		
		for(int i = v; i <= n; i++) {
			visit[i] = true;
			dfs(i + 1, d + 1);
			visit[i] = false;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true) {
			line = br.readLine().split("\\s");
			n = Integer.parseInt(line[0]); visit = new boolean[n+1];
			
			if(n == 0) break;			
			dfs(1, 0); System.out.println();
		}
	}
}