[BOJ]11051_이항계수2

11051_이항계수2

풀이

이항계수의 값들을 삼각형의 표로 나타낸 것을 파스칼의 삼각형이라고 한다.

이 문제는 N이 최대 1000으로 O(N^2)시간의 알고리즘을 구성해야 한다. 따라서 바텀업(Bottom-up) 방식으로 이항 계수를 구현했다. MOD계산을 해주는 것도 잊으면 안된다.

위 식을 이용하여 2차원 DP로 풀었다.

k가 0이거나 n과 같을 때 1이 나오는 것과, dp[0][0] = 1인 것을 신경써주면 바로 풀린다.

코드

import sys

n, k = map(int, sys.stdin.readline().split())
dp = [[1 for _ in range(k+1)] for _ in range(n+1)]

for i in range(1, k+1):
    for j in range(i+1, n+1):
        dp[j][i] = (dp[j-1][i-1] + dp[j-1][i]) % 10007

print(dp[n][k])