Q. (X)

---

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼
의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3
1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
3 1 2 4
4 3 6
7 9
16
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하
시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
▣ 입력설명
첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의
미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.
▣ 출력설명
첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재
하지 않는 경우는 입력으로 주어지지 않는다.
▣ 입력예제 1
4 16
▣ 출력예제 1
3 1 2 4

전략

• (n개 중 n개를 뽑는) 중복 아닌 순열 중 16을 만들 수 있는 순열을 찾으면 됨
• 직접 시뮬레이션 할 필요없이 공식 이용
  -> 미리 조합수(combi) 값을 구해놓은 다음 순열의 각 원소와 곱하고, 해당 각 값을 모두 더한 값이 16이 되어야한다.
• 중복되지 않아야하므로 ch배열 필요

정답

import java.util.*;
class Main{
	// b : combi 값 저장
	// p : 순열 저장
	// ch : 중복되지 않는 순열이므로 ch 필요 
	static int[] b, p, ch;
	static int n, f;
	static boolean flag = false;
	int[][] dy = new int[35][35];
	public int combi(int n, int r){
		if(dy[n][r]>0) return dy[n][r];
 		if(n == r || r == 0) return 1;
		else return dy[n][r] = combi(n-1, r-1) + combi(n-1, r);
	}
	
	public void DFS(int L, int sum){
		if(flag) return;
		// (n개 중에서) n개를 뽑은 순열 하나 완성 
		if(L == n){
			if(sum==f){
				for(int x : p) System.out.print(x+" ");
				// 답을 찾았으니까 
                // 앞으로의 재귀를 모두 멈춘다 
                // (이미 쌓여있던 스택으로 복귀해서 호출한 재귀를 바로 리턴) 
                // 복귀해서 호출한 재귀 분 외에는 새롭게 뻗지 않음
				flag = true;
			}
		}
		else{
			// i는 순열의 원소 자체이므로 1~n까지("가장 윗줄에 1부터 N까지의 숫자가~") 돌아야함
			for(int i=1; i<=n; i++){
				if(ch[i]==0){
					ch[i] = 1;
					// i는 순열의 원소 자체이다.
					p[L] = i;
					DFS(L+1, sum+(p[L]*b[L]));
					ch[i]=0;
				}
			}
		}
	}	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt(); 
		f = kb.nextInt(); 
		b = new int[n]; 
		p = new int[n];
		// "가장 윗줄에 1부터 N까지의 숫자가~" : for문의 i가 1부터 시작하므로 ch도 1부터 시작
		ch = new int[n+1];
		
		// b 배열에는 3C0, 3C1, 3C2, 3C3값이 저장된다.
		for(int i=0; i<n; i++){
			b[i] = T.combi(n-1, i);
		}
		T.DFS(0, 0);
	}
}