[6603] 로또

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

---

import java.util.Scanner;

// 6603 로또
public class Main {
	static int [] arr;
	static int N;
	static int [] ans;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			N = sc.nextInt();
			if(N == 0) break;
			arr = new int[N];
			ans = new int[N];
			for(int i=0; i<N; i++) {
				arr[i] = sc.nextInt();
			}
			recur(0,0);
			System.out.println();
		}
	}
	
	public static void recur(int start, int depth) {
		
		if(depth == 6) {
			for(int i=0; i<6; i++) {
				System.out.print(ans[i] + " ");
			}
			System.out.println();
			return;
		}
		
		for(int i=start; i<N; i++) {
			ans[depth] = arr[i];
			recur(i+1, depth+1);
		}
	}

}

---

백트래킹을 공부한 적이 없다보니, 내가 직접 풀지는 못하고 구글링을 해서 풀었다. 처음에는 짧은 코드임에도 불구하고 코드가 이해가 되지 않았다. recur 함수 안에 for문에서 계속 재귀함수가 호출되었기 때문에 하나하나 계속 적어가면서 이해를 했다. 주어진 예제에서 첫번째 예제인 7 1 2 3 4 5 6 7 을 가지고 이해 해 보자. depth 가 6일 때 백트래킹을 해주어서 오름차순으로 숫자를 출력한다. depth가 뜻하는 의미는 어느 깊이 까지 들어가느냐 하는 것이다. 여기서는 6개를 출력해야 하므로 6까지 들어가야 하는데, depth 가 6일때 함수를 return 해주어 백트래킹 해준다.

① 처음에는 1부터 차례대로 ans 배열에 첫번째 인덱스부터 들어가서 1부터 6이 출력된다.

② 1부터 6이 출력되었으면 백트래킹 되어 depth 가 5일때 7을 넣어주고 다시 recur 함수를 호출하는데,

depth가 6이 되므로 1 2 3 4 5 7을 출력한다.

처음 보면 이해하기 어렵기 때문에, 먼저 코드를 보고 차근차근 어떻게 변수가 움직이는지 보면서 이해하고,

그림을 보면 이해가 더 잘 될 것이다.