평범한 개발 일지

본 문제는 간단한 DP문제이다. 특히, 점화식이 존재하기 때문에 더 쉽다. 문제
나 같은 경우에는 처음에 dp가 아닌 그냥 때려 박았는데... 컴파일 에러가 발생했다. 그 이유는 1000!가 long long 을 사용하더라도 한참 벗어나는 어마 무시하게 큰 값이기 때문이다.
따라서 여기서는 파스칼의 삼각형을 사용해서 풀어야 한다.즉, 간단하게 설명하면
nCk = n-1Ck + n-1Ck-1 이다.

전체적인 코드는 밑과 같다

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define SIZE 1001
using namespace std;

int n, k;
int dp[SIZE][SIZE] = { 0 };

void input() {
    scanf("%d %d", &n, &k);
}

void solve() {
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 2; i < SIZE; i++) {
        dp[i][0] = 1;
        for (int j = 1; j < i; j++)
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 10007;
        dp[i][i] = 1;
    }
}

void print() {
    printf("%d", dp[n][k]);
}
int main(void) {
    input();
    solve();
    print();
}