[BOJ] 11051번 : 이항 계수 2

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n, k; 
int d[1005][1005]; 
const int val = 10007;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k; 
	for (int i = 0; i <= n; i++) {
		d[i][0] = 1; 
		d[i][i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			d[i][j] = (d[i - 1][j - 1] % val + d[i - 1][j] % val) % val;
		}
	}
	cout << d[n][k] << '\n';
}

조합의 성질을 이용하여, nCk = n-1Ck-1 + n-1Ck 풀었다. 

이 성질을 이용하여 dp를 사용했다. 따라서 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d[i][j]는 iCj를 나타낸다. 

2. 점화식을 작성한다. 조합의 성질을 이용하여, d [i][j] = d [i-1][j-1] + d [i-1][j]를 작성한다. 

3. 초기값을 설정한다. d[i][0] , d [i][i] = 1로 설정한다.