개발 다이어리

코드

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

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

경우의 수, nCr는 (n-1Cr-1)+ (n-1Cr) 와 같다는 공식을 사용한다.

n은 요소의 개수, r은 그 중 몇 개 선택할지

그리고 n==r 인 경우 경우의 수는 1, 요소가 3개에 3개를 선택한다면 경우의 수는 1개 뿐

r==0 인 경우도 경우의 수는 1이다, 요소가 아무리 많아도 0개를 선택할 경우의 수는 1개 뿐

6C4는 15의 경우의 수가 나온다.

코드

class 조합의경우수$메모이제이션{
	static int[][] dy=new int[35][35];
	static int cnt1,cnt2;
	
	static int DFS1(int n, int r){
		cnt1++;
		if(n==r || r==0) return 1;
		else return DFS1(n-1, r-1)+DFS1(n-1, r);
	}
	
	static int DFS2(int n, int r){
		cnt2++;
		if(dy[n][r]!=0) return dy[n][r]; //이미 계산해놓은게 있다.
		if(n==r||r==0) return 1;
		else {
			return dy[n][r]=DFS2(n-1,r-1)+DFS2(n-1,r);
		}
		
	}
	
	public static void main(String[] args){
		int n=6;
		int r=4;
		
		System.out.print("메모이제이션 사용 안함 ");
		System.out.println(DFS1(n, r)+" "+cnt1);
		System.out.print("메모이제이션 사용 함 ");
		System.out.println(DFS2(n, r)+" "+cnt2);
	}
}

결과

메모이제이션 사용 안함 15 29
메모이제이션 사용 함 15 17

숫자가 적어서 메모이제이션 효과가 미미해보이지만 아래처럼 조금만 증가해도 기하급수적으로 반복호출하게 된다.

메모이제이션 사용 안함 30045015 60090029
메모이제이션 사용 함 30045015 401