[백준] 11051 - 이항 계수 2 [Python(파이썬)]

문제

www.acmicpc.net/problem/11051

11051번: 이항 계수 2

풀이

이항 계수라는 개념을 모르면 풀기가 어려운 문제였다.

비슷한 문제인 이항 계수 1 같은 경우 N이 최대 10으로 작기 때문에 재귀적으로 코드를 작성하거나 itertools모듈을 이용해도 풀이가 가능했다. 

 

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

코드

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])