[Python][백준][11051] 이항 계수 2 (DP)

🍋 문제링크

11051번: 이항 계수 2

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 204292 KB

시간 : 268 ms

 

🍓 문제풀이

k 가 0 일때! 빼먹지 않을 것!!

🍉 Code

재귀로 푸니까 시간초과남...ㅠ

<시간초과난 코드>

N, K = map(int, input().split())

def recursion(n, k):
    if n == k:
        return 1
    if k == 1:
        return n
    return recursion(n-1, k-1) + recursion(n-1, k)

print(recursion(N, K))

 

<맞은 코드>

N, K = map(int, input().split())
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(0, N+1):
    for j in range(0, N+1):
        if j == 0:
            dp[i][j] = 1
        elif i == j:
            dp[i][j] = 1
        elif j == 1:
            dp[i][j] = i
        elif N >= K:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]


print(dp[N][K] % 10007)