BOJ 백준온라인져지 11051 이항 계수 2 풀이

저번에 푼걸로는 못 푼다고한다.

그래서 위키백과에서 설명하는 점화식을 사용해서 풀었다.

nCr = n-1Cr-1 + n-1Cr

1. memoization

문제

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

입력

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

출력

 $(\genfrac{}{}{0ex}{}{N}{K})$를 10,007로 나눈 나머지를 출력한다.