[백준_6603번] 로또

https://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이 하나 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_6603 {
	static boolean[] visited=new boolean[50];
	static int k;
	static int[] num;
	public static void main(String[] args) {		
		Scanner sc=new Scanner(System.in);
		
		while(true) {
			k=sc.nextInt();
			
			// 0을 입력받으면 프로그램 종료
			if(k==0)
				System.exit(0);
			
			// 로또 숫자 입력 받기
			num=new int[k];
			for(int i=0;i<k;i++)
				num[i]=sc.nextInt();
			
			dfs(0,0);
			// 각 테스트케이스 마다 한 줄 띄기
			System.out.println(); 
		}
	}
	
	// 백트래킹
	public static void dfs(int depth, int start) {
		// 숫자를 6개를 선택했다면
		if(depth==6) {
			for(int i=0;i<k;i++) {
				// 방문처리 된 숫자들만 출력
				if(visited[i]==true)
					System.out.print(num[i]+" ");
			}
			System.out.println();
			return;
		}
		
		// 백트래킹
		for(int i=start;i<k;i++) {
			visited[i]=true; // 방문처리
			/*
			 * 중복된 숫자를 선택할 수 없기 때문에 
			 * 재귀호출을 할 경우 i+1 부터 탐색을 해야한다.  
			 */
			dfs(depth+1,i+1);
			// 재귀호출이 끝난다면 다음 경우의 수를 위해 값을 되돌린다.
			visited[i]=false;
		}
	}
}

 

[고찰]

 이번 문제는 이전에 여러번 풀어보았던 백트래킹 문제 중 간단한 유형의 한 문제이다. 입력받은 숫자들 중 중복되지 않게 6개의 숫자를 선택, 방문처리 하고, 방문처리 된 숫자들만 출력해주면 된다.