BOJ #11051 이항 계수 2

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 #11051 이항 계수 2

문제 풀이

$\binom n x$이 $\binom {n-1} {r-1} + \binom {n-1} {r}$임을 알아야 풀 수 있는 문제였다. 해당 공식은 파스칼 삼각형으로 간단히 알 수 있다. 그러면 초항을 잡아야 하는데 n = r이거나 r = 0이면 1을 고정값으로 갖는다. 따라서 재귀호출로 구현하되 종료 조건을 n = r 혹은 r = 0이면 1을 리턴하도록 하면 된다. 다만, 재귀호출로만 구현하면 이미 구했던 조합도 다시 구하게 되어 시간초과를 출력하니 배열을 생성하여 이미 구했던 값이면 다시 계산하지 않도록 한다.

python 코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def solve():
    N, K = map(int, input().split())
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    def pascal(n, r):
        if n == r or r == 0:
            return 1
        if dp[n][r] > 0:
            return dp[n][r]
        dp[n][r] = (pascal(n - 1, r - 1) + pascal(n - 1, r)) % 10007
        return dp[n][r]
    print(pascal(N, K))
solve()