[11051] 이항 계수 2

---

원래는 팩토리얼로 문제를 풀었으나, N의 범위가 커지면서 쓸 수 없게 되었다

그래서 알고리즘 설계 때 배운 DP(동적 프로그래밍)을 떠올리며 문제를 풀었다 ( 시험에서는 틀렸다 ㅡㅡ )

 

DP(Dynamic Programming) : 하나의 큰 문제를 여러 개의 작은 문제로 쪼갠 다음, 과거에 구한 해를 활용하는 알고리즘

 

이항계수는 nCk로 나타낼 수 있는데, 2차원 배열로 만들었다

이항 계수 하면 떠오르는 그림을 그려보고, 행과 열을 따져보아서 값이 어떻게 들어가는지 생각해보았다

nCk = n-1Ck-1 + n-1Ck를 이용하여 dp 점화식을 세웠다

 

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

 

만든 점화식을 for문을 이용하여 구현하였다

dp[i][0]과 dp[i][i]은 항상 1이기 때문에 초기화를 해주었다

 

수가 너무 크기 때문에 10007로 나눈 나머지를 구해야 한다

그래서 저 점화식에 '%10007'을 써주었다

 

 

그렇게 완성된 코드는 다음과 같다

#include <iostream>
using namespace std;

int N, K;
int dp[1001][1001];

int f(int n, int k) {

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

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

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

	return dp[n][k];
}


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

	cin >> N >> K;

	printf("%d", f(N,K));


}