[백준] 11051-이항계수2

문제링크:https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

이항계수를 출력하는 문제입니다. 

당연히 팩토리얼을 계산해서 푸는 방식이 아닙니다. 팩토리얼 방식으로 하면, 곱하기 과정에서 아주 큰 값이 나오게 되기 때문에 오버플로우가 발생합니다. (int, longlong 둘다) 

중간중간에 나머지를 해주는 방식도 생각해보았지만, 어떠한 규칙을 적용해야할지 모르겠네요..

dp문제입니다.

dp란? 순차적인 결과물에서 특정 점화식에 의해서 값이 도출되는 형태를 의미합니다.

 

아래 그림은 파스칼 삼각형입니다. 이항계수를 구할 때 사용됩니다. 

 

감이 오시나요?

dp알고리즘의 핵심은 점화식 구하기 입니다. 

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] << 라는 점화식을 구하실 수 있을거에요

 

아래는 정답코드입니다. 아마 구현하는데 어려움은 없을실 겁니다. 

 

 

#include <iostream>
using namespace std;

int n = 0, k = 0;
int dp[1002][1002] = { 0 };

int main() {
	cin >> n >> k;

	for (int i = 1; i <= n + 1; i++) {
		dp[i][1] = 1, dp[i][i] = 1;
		for (int j = 2; j <= i - 1; j++) {
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			dp[i][j] %= 10007;
		}
	}
	cout << dp[n + 1][k + 1] << '\n';
}