[백준] 11051번 > 이항 계수 2

www.acmicpc.net/problem/11051

11051번: 이항 계수 2

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

출력

 (NK)를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

5

2

예제 출력 1

10

 

---

풀이

이항 계수1 과 같은 방식으로 구현하니 (RecursionError)가 발생하여, factorial을 외장함수로 풀었더니 맞았다.

from math import factorial
n, k = map(int, input().split())
result = factorial(n) // (factorial(k) * factorial(n - k))
print(result % 10007)

근데 풀고나니 DP로 푸는 문제여서, 다시 풀어보았다.

파스칼의 삼각형을 통하여 구현하는 것이다.

n, k = map(int, input().split())
dp = [[0] * 1 for i in range(1001)]
dp[1].append(1)
for i in range(2, 1001):
    for j in range(1, i + 1):
        if j == 1:
            dp[i].append(1)
        elif j == i:
            dp[i].append(1)
        else:
            dp[i].append(dp[i - 1][j - 1] + dp[i - 1][j])
print(dp[n + 1][k + 1] % 10007)

이것이 파스칼의 삼각형이다.