#11051번 이항 계수2 (C++)

링크 : www.acmicpc.net/problem/11051

11051번: 이항 계수 2

파스칼의 삼각형을 활용하여 풀었다.

단번에 떠올리진 못했고, 다른 사람의 풀이책을 참고하여 해결원리가 파스칼의 삼각형임을 깨달았다. 

 

#include<iostream>
#define MAX 1001
#define MODULAR 10007
using namespace std;

int ans[MAX][MAX];

void init(int n) {
	for (int i = 1; i <= n; i++) {
		ans[i][0] = 1; 
		ans[i][i] = 1;
	}
}

int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	
	int n = 0, k = 0;
	cin >> n >> k;

	init(n);
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ans[i][j] = (ans[i - 1][j - 1] + ans[i - 1][j]) % MODULAR;
		}
	}
	cout << ans[n][k] % MODULAR << "\n";
	return 0;
}