조합

문제

2407번: 조합

문제 설명

nCm을 출력한다.

제한 사항

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

입출력 예

입력	출력
100 6	1192052400

아이디어

nCm = n-1Cm-1 + n-1Cm 점화식 이용

매우 큰 수가 나오기 때문에 BigInteger 사용

제출 코드

import java.io.IOException;
import java.math.BigInteger;
import java.util.Scanner;

public class three2307 {
    BigInteger[][] dp = new BigInteger[101][101];

    public void solution() throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        for (int i = 0; i <= 100; i++) {
            dp[i][0] = BigInteger.ONE;
            dp[i][i] = BigInteger.ONE;
        }

        for (int i = 2; i <= 100; i++) {
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1].add(dp[i - 1][j]);
            }
        }
        System.out.println(dp[n][m]);
    }

    public static void main(String[] args) throws IOException {
        new three2307().solution();
    }
}