조합수(메모이제이션)

 

n개 중에 c개를 뽑는 가짓 수를 의미한다.

 

import java.util.*;

public class Main {
    //메모이제이션 사용해야 재귀가 많이 안 뻗음!!!
    //구한 값을 다시 안구한다!
    int[][] dy = new int[35][35];

    public int DFS(int n, int r){
        //메모이제이션!!!
        if(dy[n][r] > 0) return dy[n][r];
        //1을 리턴하는 경우
        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));
    }
}