📌 Problem.

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

주어진 정수 N, K에 대해 이항계수 $_NC_K$를 구하는 문제이다.

📌 Solution.

1. 재귀

import sys

input = sys.stdin.readline
N, K = map(int, input().split())

def binomial(N: int, K: int) -> int:
    if K == 0 or N == K:
        return 1
    return binomial(N - 1, K) + binomial(N - 1, K - 1)

print(binomial(N, K))

재귀로 푸는 경우, 같은 계산을 여러 번 하는 경우가 발생한다.
가령 $_4C_2$ = $_3C_2$ + $_3C_1$ = $_2C_2$ + $_2C_1$ + $_2C_1$ + $_2C_0$ = ... = 6
에서 같은 값인 $_2C_1$을 두 번 계산하는 경우처럼 말이다.

N, K 값이 클수록 재귀답게 이러한 비효율성은 극대화된다.
따라서 동적 계획법을 통해 효율적으로 값을 계산할 수 있다.

2. 동적 계획법

import sys

input = sys.stdin.readline
N, K = map(int, input().split())
dp = [[0] * 11 for _ in range(11)]

def binomial(N: int, K: int) -> int:
    if K == 0 or N == K:
        dp[N][K] = 1
    elif not dp[N][K]:
        dp[N][K] = binomial(N - 1, K) + binomial(N - 1, K - 1)
    return dp[N][K]

print(binomial(N, K))