05.12. 이항 계수 2 [Dynamic Programming][백준 11051]

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

11051번: 이항 계수 2

 

Algorithm classification : Dynamic Programming

 

05.12.1. Problem

Write a program to find the remainder of dividing a binomial coefficient 

by 10,0007 given a natural number N and an integer K.

 

05.12.2. Input limit

N and K are given in the first line. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

 

05.12.3. Output

Output the remainder after dividing by 10,007.

 

05.12.4. Solution

이항계수는 잘 알려진 점화식이 있습니다. 파스칼 삼각형을 떠올리신다면 좋을 것 같군요. 팩토리얼 계산으로 제한시간 내에 input limit을 만족시키긴 어려울 겁니다. 

 

DP table[N][K] = DP table[N - 1][K - 1] + DP table[N - 1][K]

 

	for(i = 0; i <= n; i++){
		for(j = 0; j <= i; j++){
			if(j == 0 || i == j) a[i][j] = 1;
			else a[i][j] = (a[i-1][j-1] + a[i-1][j]) % 10007;
		}
		
	}

	printf("%d", a[n][k]);