[백준 파이썬(python) 11051번 문제] (이항 계수2)

 

설명

이항계수에 대해 공부하고 삼각수의 개념을 사용해서 푸는 문제

탑 다운(재귀)와 바텀 업(반복) 두가지 방식 가능

코드

# 탑 다운 재귀 사용
import sys

sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
MOD = 10007
cache = [[False] * 1001 for _ in range(1001)]


def bino(n, k):
    if cache[n][k]:
        return cache[n][k]

    if n == k or k == 0:
        cache[n][k] = 1
    else:
        cache[n][k] = bino(n - 1, k - 1) + bino(n - 1, k)
        cache[n][k] %= MOD
    return cache[n][k]


print(bino(N, K))

# 바텀 업, 반복 사용
import sys

sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
MOD = 10007
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])