조합의 경우수

문제

고등수학에 나오는 조합에 관련된 공식이다.

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

이 글의 목적은 위의 식을 증명하는 것이 아닌 위 식을 재귀를 이용해 코드를 작성하는 것이다.

풀이

DFS 메소드를 작성해보도록 하자.

	public int DFS(int n, int r){
    	if( n == r  || r == 0)
        	return 1;
        else return DFS(n-1,r-1) + DFS(n-1, r);
    }

위의 DFS메소드를 작성하고 실행시키면 재귀만을 이용해서 푸는 것이기 때문에 시간이 오래걸린다.

위와 같이 n= 33 r = 19 인 경우 많은 시간이 소요된다.

메모이제이션을 이용하자.

    int[][] dy = new int[35][35];

를 이용해 배열을 선언하고,

      if(dy[n][r] > 0)
            return dy[n][r];

배열을 이용해 풀어주면 된다.

소스코드

package dfs_bfs;

import java.util.Scanner;
public class Main19 {
    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) {
        Main19 T  = new Main19();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int r = kb.nextInt();
        System.out.println(T.DFS(n, r));
    }
}