11051번 - 이항 계수 2

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

11051번: 이항 계수 2

조합 문제를 dp로 풀어보았다.

규칙을 찾기 어려워서 일단 계산한 결과를 적어보았다.

 

행은 n을, 열은 k를 의미할 때 5C2(nCk)를 구하자고 해보자. 

	0	1	2	3
0	1	0	0	0
1	1	1	0	0
2	1	2	1	0
3	1	3	3	1
4	1	4	6	4
5	1	5	10	10

k가 n보다 큰 경우는 0을 넣어 계산에 영향을 미치도록 하지 않았다. 

5C2의 값은 10이다. 그런데 위의 4C1 + 4C2의 값과 동일하다. 이는 우연이 아니다.

4C1은 3C0 + 3C1이다.

 

따라서, nCk = (n-1)C(k-1) + (n-1)Ck 로 식을 구할 수 있다. 

# 이항 계수 2
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 1
for i in range(1, N+1):
    for j in range(1, K+1):
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007
print(dp[N][K] % 10007)

코드로 작성하면 이렇다. dp 배열을 초반에 1로 초기화해주는 과정도 필요하다. 왜냐하면 nC0은 1이기 때문이다!