[11051] 이항 계수 2

[11051] 이항 계수 2

문제

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

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

출력

$\begin{pmatrix}N\\K\end{pmatrix}$를 10,007로 나눈 나머지를 출력한다.

코드

#include <iostream>

using namespace std;

/* 조건 */
#define MAX_N 1000

/* 변수 */
int N, K;
int C[MAX_N+1][MAX_N+1];

/* 함수 */
int combination(int n, int k) {
    if(C[n][k] > 0) return C[n][k];
    if(n == 0) return C[n][k] = 0;
    if(n == k) return C[n][k] = 1;
    if(k == 0) return C[n][k] = 1;
    return C[n][k] = (combination(n-1, k-1) + combination(n-1, k))%10007;
}

int main() {
    /* 입력 */
    cin >> N >> K;

    /* 풀이 */
    C[0][0] = 1;
    combination(N, K);

    /* 출력 */
    cout << C[N][K]%10007;
}

풀이

[11050] 이항 계수 1 문제에서
MAX_N과 결과값을 10007로 나눈 나머지로 표현한 것 이외에는 다른게 없다.

출처

백준 [11051] 이항 계수 2
https://www.acmicpc.net/problem/11051