[Python] 백준 11051번: 이항 계수 2

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

11051번: 이항 계수 2

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
DIV = 10007
NOT_DEFINED = -1


def get_combination(n, k):
    if k == 0 or k == n:
        return 1
    if dp[n][k] == NOT_DEFINED:
        dp[n][k] = (get_combination(n-1, k-1) + get_combination(n-1, k)) % DIV

    return dp[n][k]


if __name__ == '__main__':
    N, K = map(int, input().split())
    dp = [[NOT_DEFINED]*1001 for _ in range(1001)]
    dp[0][0] = 1
    print(get_combination(N, K))

nCr = (n-1)C(r-1) + (n-1)Cr

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

 

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