[Python][백준] 11051 이항 계수 2

Overflow가 나지 않도록 범위를 잘 조절해주면서 푸는 정수론 문제이다.

(하지만 나는 그냥 Python을 사용했다.)

 

문제

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

 

입력

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

 

출력

𝑁C𝐾를 10,007로 나눈 나머지를 출력한다.

 

 

이항계수 공식은 조합 nCr 을 계산하는 것과 같지만, 아직 배우지 않았거나 기억이 안나는 사람들을 위해 아래 써놓았다.

 

코드를 살펴보자

import math
N,K = map(int, input().split())
O = math.factorial(N) // (math.factorial(N-K)*math.factorial(K))
print(O%10007)

 

• N과 K를 각각 입력받고 math 모듈의 factorial 함수를 사용해서 이항계수 공식을 사용해주었다.