문제

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

입력

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

출력

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

예제 입력

5 2

예제 출력

10

내가 했던 풀이 방법

다음과 같이 있을 때, 10을 곱하고 1로 나누고 9를 곱하고 2를 나누고...를 반복해서 풀이한다.

1. N-K와 K 중 더 작은 값으로 K를 저장해준다.
2. K가 0이 되기 전까지 result에 N을 곱하고 div를 나눠주는 것을 반복한다. 이때 N은 1씩 감소해야하고 div는 1씩 증가해야 한다.
3. result를 10007로 나눈 값을 출력한다.

코드

const fs = require('fs');
let n = fs.readFileSync(0, 'utf-8').toString();

let [N, K] = n.trim().split(' ').map(BigInt);

let result = 1n;
let div = 1n;

K = N - K > K ? K : N - K;
while (K--) {
  result *= N;
  result /= div;

  N = N - 1n;
  div = div + 1n;
}

console.log((result % 10007n).toString());

회고

이항 계수 시간초과 없이 풀이하는 방법 항상 까먹었는데 재밌고 쉽게 기억할 수 있는 방법을 찾아서 기록하기 위해!