11051번: 이항 계수 2

Memo

로직 설명

• 이항 계수 ${n\choose k}$ 는 ${nCk}$ 와 동일하므로, 조합을 구현하는데 메모이제이션 기법으로 최적화 했습니다.

시간

pypy3 기준으로 가장 빠른 시간은 100ms입니다. (저는 372 ms)

수식으로 표현이 가능해 보입니다. 이는 재귀적으로 함수를 호출하고 함수 내에서 비교연산, 대입연산, 산술 연산 등이 포함된 제 코드가 시간이 더 걸리는 이유입니다.

Code

제출 날짜

2021/04/25

import sys

N, K = map(int, sys.stdin.readline().split())
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
def combination(n, k):
    if (n == k or k == 0):
        return 1
    if dp[n][k]:
        return dp[n][k]
    dp[n][k] = combination(n - 1, k) + combination(n - 1, k - 1)
    return dp[n][k]

print(combination(N, K) % 10007)