[🥈1 / 백준 11051 / 파이썬] 이항 계수 2

 

11051번: 이항 계수 2

 

문제

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

입력

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

출력

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

 

예제 입력 5 2

예제 출력 10

 

풀이

 

이번 문제에선 입력의 범위가 10에서 1000으로 늘어났다.

 

1000팩토리얼은 어마어마하게 큰 숫자이기 때문에 당연히 메모리초과가 일어날 것이다.

 

 

이항 계수의 식을 확인해 보자.

 

n! 으로 나열될 숫자가 만약 분모에 존재한다면 약분이 가능하다.

 

굳이 분자를 모두 계산한 뒤 분모를 모두 계산하고 이를 나눠줄 필요가 없다는 말이다.

 

분자에서 서로 곱하기 전의 리스트를 만든 뒤에 분모도 마찬가지로 만들어주고

 

약분한 뒤 계산하도록 하자.

 

n, k = map(int,input().split())

def factorial(num):
    result = []
    for i in range(2, num+1):
        result.append(i)
    return result
    # 곱해주어야 할 숫자들의 리스트를 반환한다.

k = factorial(k) + factorial(n-k)
n = factorial(n)
# 순서에 유의. k가 먼저

while(True):
    for i in n:
        if i in k:
            n.remove(i)
            k.remove(i)
            break
    else:
        break
# 겹치는 것 모두 약분

result = 1
for i in n:
    result *= i
for i in k:
    result //= i
print(result%10007)