조합 구하기(메모리제이션)

nCr = (n-1)C(r-1) + (n-1)C(r) 조합공식을 이용해서 조합 값 구하기

nCr에서 n=r이나 r이 0이되면 1을 리턴하니 dfs로 구하는 코드를 짜면 

 

    public int dfs(int n, int r){
        //nCr에서 n=r이나 r이 0이면 1
        if (n == r || r == 0) return 1;
        else return dfs(n-1,r-1) + dfs(n-1,r);
    }

코드는 간단하지만 숫자가 커지면 너무 비효율적이다

계산 결과를 저장해뒀다가 쓰는 메모리제이션으로 계산 결과가 같은 건 저장해둬서 효율적으로 써보자

 

    public int dfs(int n, int r){
        // 이미 nCr할 값을 구해서 배열에 저장해뒀으면
        if (ch[n][r] > 0 ) return ch[n][r];

        //nCr에서 n=r이나 r이 0이면 1
        if (n == r || r == 0) return 1;
        else return ch[n][r] = dfs(n-1,r-1) + dfs(n-1,r);
    }

앞에 피보나치 수열 구할 때 처럼 값을 return ch[n][r] = dfs(n-1,r-1) + dfs(n-1,r); 형태로 저장해두고

이미 구한 값이면 더 깊이 탐색을 하지 않고 저장해둔 값을 리턴한다

 

전체 코드

 

import java.util.*;
class Main{
	int[][] dy=new int[35][35];
	public int DFS(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]=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);
		int n=kb.nextInt();
		int r=kb.nextInt();
		System.out.println(T.DFS(n, r));
	}
}