11051번: 이항 계수 2

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

파스칼의 삼각형 법칙에 따라 이항계수 nCk는 k가 0 혹은 n일 때 1, 그 외의 경우에는 (n - 1)C(k - 1) + (n - 1)Ck이다.

#include <cstdio>

#define MAX_N 1000
#define MOD 10007

int main() {
    // N, K: 이항계수 상수
    int N, K;
    // ans[n][k]: 이항계수 nCk
    short ans[2][MAX_N + 1] = {{ 0, }};

    // 문제의 조건을 입력받은 뒤 파스칼의 삼각형을 이용해 이항 계수를 계산
    scanf("%d %d", &N, &K);
    for (int n = 1; n <= N; n++) {
        ans[n % 2][0] = ans[n % 2][n] = 1;
        for (int k = 1; k < n; k++)
            ans[n % 2][k] = (ans[!(n % 2)][k] + ans[!(n % 2)][k - 1]) % MOD;
    }

    // 이항계수를 출력
    printf("%hd\n", ans[N % 2][K]);

    return 0;
}