[Java] 백준 2407번 : 조합

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

예제 입력 1

100 6

예제 출력 1

1192052400

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N, M;
	private static BigInteger [][]dp;
	public static void main(String[] args) throws IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(bf.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		dp=new BigInteger[N+1][N+1];
		
		for(int i=1;i<=N;i++) {
			for(int j=0;j<=i;j++) {
				if(i==j || j==0) dp[i][j]=new BigInteger("1");
				else dp[i][j]=dp[i-1][j-1].add(dp[i-1][j]);
			}
		}
		
		System.out.println(dp[N][M]);
	}

}

nCm은 n값이 13만 되어도 1억이 넘는 매우 큰 수가 될 수 있습니다. 따라서 BigInteger를 이용해주어야 합니다.

또한 시간 초과가 나지 않으려면 dp를 이용하여 이전에 저장된 값을 이용해서 계산해주어야 합니다.