08. 수열 추측

 

설명

수열 추측

 

 

 

풀이

 

check배열 필요하고

3C0 3C1 3C2... 담을 b 배열도 필요하다

그리고 순열 담아놓을 m 배열도 필요하다.

 

 

 

1. 맨 처음에 b 배열은 Combi 함수 돌려서 다 채워넣는다.

 

2. 그리고 int DFS돌리는데 순열 구하듯이 하면 된다. 하지만 sum+(b[L]*m[L])이다.

 

import java.util.*;
class Main {
	static int n, f;
	static int[][] arr = new int[35][35];
	static int[] check; 
	static int[] b;
	static int[] m;
	boolean flag= false;
	
	public int Combi(int n, int r) {
		if(arr[n][r]>0) {
			return arr[n][r];
		}
		if(r==0 || n==r) {
			return 1;
		}else {
			return arr[n][r]= Combi(n-1,r-1)+Combi(n-1,r);
		}
	}
	
	public void DFS(int L, int sum) {
		
		if(flag) {
			return;
		}
		if(L==n) {
			if(sum==f) {
				for(int i=0; i<n; i++) {
					System.out.print(m[i]+" ");
					flag=true;
				}
			}
		}
		else {
			for(int i=1; i<=n; i++) {
				if(check[i]==0) {
					check[i]=1;
					m[L]=i;
					DFS(L+1,sum+(b[L]*m[L]));
					check[i]=0;
				}
			}
		}
		
	}
	
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		f=kb.nextInt();
		check= new int[n+1];
		m= new int[n];
		b= new int[n];
		
		for(int i=0; i<n; i++) {
			b[i]=T.Combi(n-1, i);
		}
		
		
		T.DFS(0,0);

	}	
}