문제

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

import sys

input = lambda: sys.stdin.readline().strip()

n, k = map(int, input().split())
arr = [1] * (n+1)
for i in range(1, n+1):
  arr[i] = arr[i-1] * i

com = arr[n] // (arr[n-k] * arr[k]) % 10007

print(com)

풀이

• N K -> nCk = n! / ((n-k)! * k!)
• n! 을 저장해 불러오기 - 메모이제이션 방법 사용

백준 11051 이항 계수 2