[백준] 11051번: 이항 계수 2

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

11051번: 이항 계수 2

이항계수를 구하는 문제. 간단하게 생각해서 1~N까지의 팩토리얼을 구해서 배열에 저장하면 되지 않을까 생각했지만, 1000!은 long long의 표현 범위조차 아득히 넘어버린다. 따라서 nCr = n-1Cr-1 + n-1Cr 이라는 조합 공식을 이용해야 한다.

include <iostream>
using namespace std;

int dp[1001][1001];

int main(void) {
	int N;
	int K;
	cin >> N >> K;

	for (int i = 0; i <= N; i++) {
		dp[i][0] = 1;
	}

	for (int i = 1; i <= K; i++) {
		for (int j = i; j <= N; j++) {
			dp[j][i] = (dp[j - 1][i - 1] + dp[j - 1][i]) % 10007;
		}
	}

	cout << dp[N][K];
}

먼저 1001*1001짜리 dp 배열을 선언하고, k가 0인 경우를 모두 1로 초기화해준다.

그리고 for문을 돌며 공식에 맞게 dp를 채워주면 된다.

N은 K보다 무조건 같거나 크므로, j의 index를 i부터 시작해주었다.