문제

조합수를 구하세요.
5C2 = 1,2,3,4,5의 숫자중 2개의 숫자를 뽑아 조합할 수 있는 개수

조합수의 공식
nCr = (n-1)C(r-1) + (n-1)C(r)

코드

public class CombinationNumber {
    static int[][] memo = new int[35][35];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
        memo = new int[n+1][n+1];
        System.out.println(dfs(n,r));
    }
    public static int dfs(int n, int r){
        if(n==r || r==0){
            return 1;
        }else{
            if(memo[n][r] != 0) return memo[n][r];
            return memo[n][r] = dfs(n-1, r-1) + dfs(n-1, r);
        }
    }
}

설명

조합수라는 수학적 개념을 알고리즘으로 풀어내는 문제였다. dfs의 문제 방식을 익혔다고 생각했었는데. 지금까지는 뻗어나가는 dfs 문제 풀이를 위주로 풀어서 그런지 공식에 dfs를 대입하는 방식을 바로 떠올리지 못했다.

조합수라는 수학적 개념을 익히고 넘어가면 좋을거 같다.

규칙이 있는 공식 + 규칙이 있는 공식 = dfs(규칙) + dfs(규칙)