[JAVA] 백준 6603 - 로또

 

 

🤔 문제 접근

dfs를 사용하는 조합 문제였다.

다만 숫자의 자리가 6자리로 고정되어있고 숫자의 구성이 사전 순으로 되어있음을 고려해야한다.

따라서 재귀 호출을 한 횟수가 6일 때 StringBuilder에 append 해주고

사전 순을 고려할 땐 이전에 고른 idx를 파라미터로 넘겨주어 해당 idx+1을 해주도록 했다.

 

다른 비슷한 문제들 같은 경우 boolean 타입의 visit 배열로 중복체크를 하지만

해당 문제는 어차피 이전에 고른 숫자 idx + 1을 골라주기 때문에 boolean으로 중복체크를 할 필요가 없었다.

 

🚨CODE

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int k;
	static String[] nums;
	public static void main(String[] args) throws Exception  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			k = Integer.parseInt(st.nextToken());
			if(k == 0)
				break;
			
			nums = new String[k];
			
			for(int i = 0; i<k; i++) {
				nums[i] = st.nextToken();
			}
			
			for(int i = 0; i<nums.length-6; i++) {
				dfs(nums[i], 0, i);
			}
			
			// 마지막 숫자 조합 선택
			for(int i = nums.length-6; i<nums.length; i++) {
				sb.append(nums[i]).append(" ");
			}
			
			sb.append("\n");
			sb.append("\n");
		}
		System.out.println(sb);
	}
	public static void dfs(String str, int depth, int idx) {
		if(depth == 5) {
			sb.append(str).append("\n");
			return;
		}
		
		for(int i = idx+1; i<nums.length; i++) {
			dfs(str.concat(" ").concat(nums[i]), depth+1, i);
			
		}
		
	}
}