악곱 == 악성곱슬

수학, 다이나믹 프로그래밍

---

이항 계수란 (x+y)^N을 전개했을 때 나오는 식의 계수를 의미한다. 1, 11, 121, 1331, 14641 등의 피라미드 구조를 쌓으며 진행된다. 이는 nCk의 조합으로 나타낼 수 있다. 이는 트리구조를 나타내며 간단하게 n-1Ck-1 + n-1Ck 로 구할 수 있다. 따라서 다이나믹 프로그래밍을 이용하여 구할 수 있다. N이 커질수록 재귀가 깊어지므로 DP테이블을 이용하여 시간복잡도를 개선한다.

코드는 아래와 같다.

import sys

# def binomial_coefficient(n, k):
#     if k == 0 or k == n:
#         return 1
#     return binomial_coefficient(n-1, k-1) + binomial_coefficient(n-1, k)

def binomial_coefficient(n, k):
    if k == 0 or k == n:
        memoization[n][k] = 1
        return memoization[n][k]
    if memoization[n-1][k-1] == 0:
        memoization[n-1][k-1] = binomial_coefficient(n-1, k-1)
    if memoization[n-1][k] == 0:
        memoization[n-1][k] = binomial_coefficient(n-1, k)
    return memoization[n-1][k-1] + memoization[n-1][k]

if __name__ == "__main__":
    sys.setrecursionlimit(100000)
    N, K = map(int, sys.stdin.readline().rstrip().split())
    memoization = [[0]*(K+1) for _ in range(N+1)]
    print(binomial_coefficient(N, K))