Memo
로직 설명
•
이항 계수 는 와 동일하므로, 조합을 구현하는데 메모이제이션 기법으로 최적화 했습니다.
시간
pypy3 기준으로 가장 빠른 시간은 100ms입니다. (저는 372 ms)
수식으로 표현이 가능해 보입니다. 이는 재귀적으로 함수를 호출하고 함수 내에서 비교연산, 대입연산, 산술 연산 등이 포함된 제 코드가 시간이 더 걸리는 이유입니다.
Code
제출 날짜
@4/25/2021
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)
Python
복사
