[JAVA/코딩테스트] 조합의 경우수(메모이제이션)

설명

로 계산합니다.

하지만 여러분은 이 공식을 쓰지않고 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.

입력

첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.

 

출력

첫째 줄에 조합수를 출력합니다.

예시 입력1 

5 3

예시 출력1

10

예시 입력2 

33 19

예시 출력2

818809200

 

 - 내가 푼 풀이

import java.util.*;

public class Main {

    static int[][] array;

    public static int fact(int n) {

        if (n <= 1)
            return 1;
        else
            return fact(n-1) * n;

    }

    public int DFS(int n, int r){

        if(n==r){
            return 1;
        }

        if(r <= 1 || n <= 1){
            int top  = fact(n);
            int bottom = fact(n-r) * fact(r);
            array[n][r] =  top / bottom;
        }

        if(array[n][r] == 0){
            array[n][r] = DFS(n-1, r-1) + DFS(n-1, r);
        }

        return array[n][r];

    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int r = kb.nextInt();

        array = new int[n+1][r+1];

        System.out.println(main.DFS(n, r));

    }

}