[11051] (C++) 이항 계수2

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

문제

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

입력

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

출력

 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다.

코드

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

int N;
int K;

long long DP[1001][1001];


int main(void) {
	cin >> N >> K;


	for(int i=0; i<=N; ++i){
		for(int j=0; j<=i; ++j){
			if(j == 0) DP[i][0] = 1;
			else if(j == i) DP[i][j] = 1;
			else{
				DP[i][j] = (DP[i-1][j-1] + DP[i-1][j]) % 10007;
			}
		}
	}

	cout << DP[N][K];
	
  return 0;
}

이 문제는 DP를 활용한 문제이다. 동적 계획법을 쓴 대표적 문제이다