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

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

초기코드

n, k = map(int,input().split())

def fun(n,k):
    if k==n or k==0:
        return 1
    else:
        return fun(n-1,k-1)+fun(n-1,k)
print(fun(n,k)%10007)

시간초과난다

재귀(메모이제이션)

import sys

n, k = map(int,input().split())
sys.setrecursionlimit(10**7)

cache = [[0]*1001 for _ in range(1001)]

def fun(n,k):
    if cache[n][k]:
    # 0이 아닌 수라면
        return cache[n][k]
    if k==n or k==0:
        cache[n][k]= 1
    else:
        cache[n][k] = fun(n-1,k-1)+fun(n-1,k)
    return cache[n][k]

print(fun(n,k)%10007)

이번엔 바텀업 방식인 반복문으로 풀어보자 (타뷸레이션)

n, k = map(int,input().split())

cache = [[0]* 1001 for _ in range(1001)]

for i in range(1001):
    cache[i][0] = cache[i][i] =1
    for j in range(1, i):
        cache[i][j] = cache[i-1][j-1] + cache[i-1][j]

print(cache[n][k] %10007)