[백준] 11051번 이항 계수 2

11051번: 이항 계수 2

파스칼의 삼각형에서 도출해낼 수 있는

이항 계수의 공식은

이다.

그런데 이대로 구현하면

nCr=nCn-r

이라는 성질 때문에 예를 들면 5C1 5C2를 구했는데

같은 값인 5C4, 5C3도 구하게 되는

불필요한 계산을 하게 된다.

그래서 삼각형을 반으로 나누어 중복되는 값을 없애보았다.

이렇게 반으로 나누면 짝수일 때 마지막 숫자만

이렇게 되고 나머지는

이 공식이 똑같이 적용된다.

이대로 구현해주면 끝

#include <iostream>
using namespace std;
int main() {
	int N, K;
	cin >> N >> K;
	int dp[1001][502] = { 0 };
	dp[0][0] = 1, dp[1][0] = 1;
	for (int i = 2; i <= N; i++) {
		dp[i][0] = 1;
		for (int j = 1; j <= i / 2; j++) {
			if (i % 2 == 0 && j == i / 2) dp[i][j] = (dp[i - 1][j - 1] * 2) % 10007;
			else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
		}
	}
	if (K > N / 2) K = N - K;
	cout << dp[N][K];
	return 0;
}