07. 조합의 경우수(메모이제이션)

 

설명

nCr=n-1Cr-1+n-1Cr

 

 

예시

5 3

 

10

 

 

33 19

 

818809200

 

 

 

풀이

1. 메모이제이션 방식을 통해 시간을 아낄수 있다.

 

2. nCr=n-1Cr-1+n-1Cr 이 공식 그대로 DFS 돌리기

import java.util.*;
class Main {
	static int n, r;
	static int[][] arr = new int[35][35];
	static int[] check; 
	static int[] pm;
	
	public int DFS(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]= DFS(n-1,r-1)+DFS(n-1,r);
		}
	}
	
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		r=kb.nextInt();
		System.out.println(T.DFS(n,r));

	}	
}