백준 11051번 이항 계수 2 C++

파스칼의 법칙을 알아야 풀 수 있는 문제

 

파스칼의 법칙은 C(n+1, k+1) = C(n, k+1) + C(n, k) 이지만

 

우리는 C(n, k)를 구해야 하므로

C(n, k) = C(n-1, k) + C(n-1, k-1) 

공식을 사용하면 된다.

 

#include <iostream>
using namespace std;

#define MOD 10007

int dp[1001][1001]{};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; ++i) {
		dp[i][0] = 1; // i개 중에서 0개를 고르는 방법의 수: 항상 1개 (아무것도 선택X)
		dp[i][i] = 1; // i개 중에서 i개를 고르는 방법의 수: 항상 1개 (전부 선택)
	}

	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j < i; ++j) 
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
			// dp[i-1][j-1] : 현재 원소를 선택하는 경우
			// dp[i-1][j] : 현재 원소를 선택하지 않는 경우
			// 둘을 더하고 10007로 나눈다

	cout << dp[n][k];

	return 0;
}