[백준 11051] 이항 계수 2 Python

이항 계수 2

• 티어 : Silver 1
• 시간 제한 : 1 초
• 메모리 제한 : 256 MB
• 알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론

문제

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

입력

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

출력

$\binom{N}{K}$를 10,007로 나눈 나머지를 출력한다.

예제 입출력

---

Algorithm

1. N * ... * 1을 총 K번 진행
2. K! 계산
3. 1번의 결과를 2번의 결과로 나눔
4. 3번의 결과를 10007로 나눈 나머지 출력

Code

import sys
sys.setrecursionlimit(10 ** 6)

# Factorial 계산하는 함수
def factorial(K):
    if K < 2:
        return 1
    else:
        return K*factorial(K-1)
    
# 입력
N, K = map(int, input().split())

# N * N-1 * ...
num1 = 1
for i in range(K):
    num1 *= N-i
    
# K!
num2 = factorial(K)

# (N * N-1 * ... // K!) % 10007
print((num1 // num2) % 10007)

메모리: 31324 KB
시간: 72 ms