[정수론 및 조합론_11051] 이항 계수 2

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

[문제]

자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

[입력 조건]

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

 

[코드]

import java.util.*;

public class BaekJoon_11051 {
	public static int n,k,div=10007;
	public static int[][] dp;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		k=sc.nextInt();
		dp=new int[n+1][k+1];
		
		System.out.println(func(n,k));
	}
	
	public static int func(int n, int k) {
		if(dp[n][k]>0)
			return dp[n][k];
		/*
		 * 이상 계수의 성질 사용
		 * nC0 = nCn =1 
		 */
		if(n==k||k==0)
			return dp[n][k]=1;
		/*
		 * 파스칼의 정리 사용
		 * nCr = n-1Ck-1 + n-1Ck 
		 */
		return dp[n][k]=(func(n-1,k-1)+func(n-1,k))%div;
	}
}

[고찰] 

 이번 문제는 이항 계수 문제를 동적 계획법으로 푸는 것이다. 이 문제를 해결하기 위해서는 이항 계수의 성질과 파스칼의 법칙을 알아야 한다. 우선 이항 계수의 성질은 아래 그림과 같다.

k==0인 경우와 n과 k가 같은 경우의 dp 값은 1로 저장한다. 기본적인 파스칼의 법칙은 아래 식과 같은데

n과 k에 각각 n-1, k-1을 대입하여 식을 정리하여 활용하면 된다. 

이 두 식을 활용하여 동적 계획법으로 문제를 풀면 시간 초과 없이 정답 처리를 받을 수 있다.