문제

BOJ 6603: 로또 https://www.acmicpc.net/problem/6603

풀이

• 문제에서 이미 그룹화를 다 해주어서 제시된 그룹 중 6개만 골라 출력해주면 되는 쉬운 문제다.
• 백트래킹 을 사용하여 제시 된 그룹 중 6개의 수를 고를 때 까지 재귀호출을 해주면 된다.

코드

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

public class Main {
	
	static int[] newArr;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int k = -1;
		
		while(k != 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			k = Integer.parseInt(st.nextToken());
			newArr = new int[6]; // 6개 고른 수를 넣을 배열
			int[] s = new int[k];
			for(int i=0; i<s.length; i++) {
				s[i] = Integer.parseInt(st.nextToken());
			}
			
			backTracking(s, 0, 0);
			
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	static void backTracking(int[] arr, int start, int depth) {
		// 6개 다 골랐으면 종료함
		if(depth == 6) {
			for(int value : newArr) {
				sb.append(value).append(" ");
			}
			sb.append("\n");
			return;
		}
		
		for(int i=start; i<arr.length; i++) {
			
			newArr[depth] = arr[i]; // 6개의 수를 모을 새로운 배열에 삽입
			backTracking(arr, i + 1, depth + 1); // 깊이를 1 증가시켜서 재귀

		}
	}

}

정리

• 재귀 호출 할 때 backTracking(arr, i, depth + 1) 이렇게 하려면 방문 처리를 해 줄 배열을 추가로 써야한다.