수열추측하기

코드

import java.util.*;

class 수열추측하기{
	static int[] b, p, ch;
	static int n, f;
	static boolean flag=false;
	static int[][] dy=new int[35][35];
	
	static 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);
	}
	
	static void DFS(int L, int sum){
		if(flag) return;
		if(L==n){
			if(sum==f){
				for(int x : p) System.out.print(x+" ");
				flag=true;
			}
		}else{
			for(int i=1; i<=n; i++){
				if(ch[i]==0){
					ch[i]=1;
					p[L]=i;
					DFS(L+1, sum+(p[L]*b[L]));
					ch[i]=0;
				}
			}
		}
	}

	public static void main(String[] args){
		n=4;
		f=16;
		b=new int[n];
		p=new int[n];
		ch=new int[n+1];
		for(int i=0; i<n; i++){
			b[i]=combi(n-1, i);
		}
		System.out.println(Arrays.toString(b));
		DFS(0, 0);
	}
}

---

결과

[1, 3, 3, 1]
3 1 2 4

---

미리 메모이제이션을 이용해서 경우의 수를 계산 후 이를 사용