이항 계수 2 (feat. 백준, 11051번)

이항 계수 2
https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/11051
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, K, dp[1001][1001];
	cin >> N >> K;
	dp[1][0] = dp[1][1] = 1;
	for (register int n = 2, k; n <= N; ++n)
		for (k = 0; k <= n; ++k)
			if (k == 0 || k == n)
				dp[n][k] = 1;
			else
				dp[n][k] = (dp[n - 1][k - 1] + dp[n - 1][k]) % 10007;
	cout << dp[N][K] << endl;
	return 0;
}
// *&)*@*

1. nCk. 즉, n개 중에 k개를 고르는 조합은 n!/(k! * (n-k)!) 의 수식을 가지고 있습니다.
2. 또한 조합은 파스칼의 삼각형이라는 성질을 그대로 가지고 있습니다.
3. 해당 문제는 dp 유형이므로 파스칼의 삼각형을 이용하기로 하였습니다.
4. 아래는 파스칼의 삼각형에 대한 방법을 정리할겸 그려봤습니다. 그 내용이 코드에 그대로 녹아져있습니다.