[BOJ 11051] 이항계수2 - 동적계획법

문제

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

사실 이항계수의 성질만 잘 알고 있다면 쉽게 풀 수 있는 문제입니다.

파스칼의 법칙? 인가요? nCr = (n-1)Cr + (n-1)C(r-1) 입니다.

#include "pch.h" #include <iostream> #include <stdlib.h> using namespace std; const int MAX = 1001; const int MOD = 10007; int N, K; int cache[MAX][MAX]; void init() { for (int i = 1; i <= N; i++) { cache[i][1] = i; cache[i][i] = cache[i][0] = 1; } } void sol() { for (int i = 3; i <= N; i++) { for (int j = 2; j < i; j++) { cache[i][j] = cache[i - 1][j] % MOD + cache[i - 1][j - 1] % MOD; } } } int main() { cin >> N >> K; if (N < 1 || N >= MAX || K<0 || K>N) exit(-1); init(); sol(); cout << cache[N][K] %MOD << endl; return 0; }