📝문제

저번에는 recursion 이용해서 Combination을 만들어봤었는데 이번에는 DP의 방식이다.
점화식은 조합 계산 공식을 비교하다보니 비교적 빠르게(?) 생각해 낼 수 있었다.

7C3의 경우 : (7 6 5) / (3 2 1)
8C3의 경우 : (8 7 6) / (3 2 1)
...
이런 방식으로 나아가는데 nCm은 (n-1)Cm에서 n을 곱하고 n-m을 나누면 된다.

처음에는 대충 큰 값이 나올거라고 생각해서 그냥 long으로 풀었는데 틀렸다는 결과가 나왔다.
long으로 표현할 수 없는 큰 수도 결과로 나오는구나를 알았고 BigInteger를 사용했다.

📌코드

package Baekjoon;

import java.math.*;
import java.util.*;
import java.io.*;

public class BOJ2407 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        /**
         * dp 배열을 만든다. 인덱스 1부터 시작
         * dp[m] = 1,
         * 점화식 : dp[i+1] = dp[i] * (i+1) / (i-m)
         */
        BigInteger[] dp = new BigInteger[n+1];
        dp[m] = new BigInteger("1");
        for(int i = m+1; i < dp.length; i++){
            dp[i] = dp[i-1].multiply(BigInteger.valueOf(i)).divide(BigInteger.valueOf(i-m));
        }
        System.out.println(dp[n]);
    }
}