[알고리즘]DFS - 수열 추측하기

 

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다.

그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.

 

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램

import java.util.Scanner;

public class Main { 
	static int n, f, answer = 0;
	static int[] a, b, ch;
	static int[][] arr; // 메모이제이션
	static boolean flag = false; // sum==f일때 바로 종료
	
	public static int combi(int n, int r) {
		if (arr[n][r]>0) return arr[n][r];
		if (n==r || r==0) return 1;
		else {
			return arr[n][r] = combi(n-1, r-1) + combi(n-1, r);
		}
	}
	
	public static void DFS(int level, int sum) {
		if (flag) return;
		if (level==n) { // 순열 완성
			if (sum==f) {
				for (int x : b) {
					System.out.print(x + " ");
					flag = true;
				}
			}
		}
		else {
			for (int i=1; i<=n; i++) { // 순열 만들기
				if (ch[i]==0) {
					ch[i] = 1;
					b[level] = i;
					DFS(level+1, sum+(a[level]*b[level]));
					ch[i] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt(); // 가장 윗줄에 있는 숫자의 개수
		f = scanner.nextInt(); // 가장 밑줄에 있는 수 
		a = new int[n]; // nCr 값
		b = new int[n]; // 맨 윗줄 수
		ch = new int[n+1]; // check 배열
		arr = new int[n+1][n+1]; // 메모이제이션 배열
		for (int i=0; i<n; i++) {
			a[i] = combi(n-1, i);
		}
		DFS(0, 0);
	}

}

---

4 16
3 1 2 4