[Python] 백준 11051번 문제, 이항 계수 2

<문제 링크>

 

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

11051번: 이항 계수 2

 

---

<풀이>

 

N과 K를 입력 받아 nCk의 결과를 출력하는 문제이다.

nCk는 n! / k!(n-k)!이다. (N과 K의 범위는 문제 참고)

 

그런데 N!, K!, (N-K)!를 구할 때 중복된 계산이 많기 때문에 비효율적이다.

그렇기 때문에 동적 프로그래밍을 이용한다면 효율적으로 계산할 수 있다.

 

나는 dp를 만들고 인덱스에 해당 팩토리얼 결과값을 넣었다.

예로 1번째 인덱스, 2번째 인덱스, 그리고 3번째 인덱스 값이 순서대로 1, 2, 6인데 3번째 인덱스 값을 구할 때, 1x2x3 할 필요 없이 2번째 인덱스 결과값 x 3만 해주면 된다.

간단하게 i의 팩토리얼 값을 구하기 위해서는 i-1번째 값에다가 i만 곱해주면 된다.

 

---

<코드>

dp[]: 팩토리얼 결과를 저장한 리스트

---

import sys


if __name__ == "__main__":
    N, K = map(int, sys.stdin.readline().split())
    dp = [1, 1, 2]

    for i in range(3, N+1):
        dp.append(dp[i-1] * i)

    print((dp[N] // (dp[N-K] * dp[K])) % 10007)