삼각수

11051번: 이항 계수 2

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

메모제이션 미사용

import sys

MOD = 10007
# Traceback (most recent call last):
sys.setrecursionlimit((10 ** 7))

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

def bino(n,k):

    if k == 0 or k == n:
        return 1

    return bino(n - 1, k - 1) + bino(n - 1, k)

print(bino(N, K))

메모제이션 사용 (top-down)

삼각수를 확인해보면 전부 양수가 들어온것을 확인 할수 가 있음

값 두개를 저장 해야 하기 때문에 cache를 2창뤈 배열로 작성

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

bino(n - 1, k - 1) + bino(n - 1, k) 의 합이 10007 미만이야 하므로

cache[n][k] %= MOD

cache[n][k] %= MOD 로 함

import sys

MOD = 10007
# Traceback (most recent call last):
sys.setrecursionlimit((10 ** 7))

cache = [[0] * 1001 for _ in range(1001)]
N, K = map(int, input().split())


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

    if k == 0 or k == n:
        cache[n][k] = 1
    else:
        cache[n][k] = bino(n - 1, k - 1) + bino(n - 1, k)
        # cache[n][k]의 값이 10007미만 초과 방지
        cache[n][k] %= MOD
    return cache[n][k]


print(bino(N, K))

잘 나오는것을 확인

메모제이션 사용 (bottom-up)

MOD = 10007


cache = [[0] * 1001 for _ in range(1001)]
N, K = map(int, input().split())

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]
        cache[i][j] %= MOD

for i in range(7):
    print(cache[i])
print()

print(cache[N][K])

삼각수 로그 및 결과 확인