[C/C++] 백준 11051번 - 이항 계수 2 (DP풀이)

 

<코드>

#include<iostream>
using namespace std;

int N, K;
long long DP[1001][1001];

//점화식 DP[N][K] =DP[N-1][K-1] + DP[N-1][K] 

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

	DP[0][0] = 1;
	DP[1][0] = 1;
	DP[1][1] = 1;

	for (int i = 2; i <= N; i++)
		for (int j = 0; j <= i; j++)
		{
			if (j == 0) DP[i][0] = 1;
			else if (j == i) DP[i][j] = 1;
			else DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j]) % 10007;
			// 매번 10007로 나눠주지 않으면 자료형의 크기를 초과하게 됨.
		}
			

	cout << DP[N][K];

}

 

 

파스칼의 삼각형

 

파스칼의 삼각형

이항 계수 항등식

파스칼 삼각형 점화식

출처 - 위키백과 (이항 계수)

 

 

쉬운 문제일 줄 알았는데 DP로 풀어야 한다는 것을 인지하지 못해서 많이 헤맸다.

초기값 세팅 후 점화식은

DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j] % 10007

위와같이 구했으며, 매 연산마다 10007로 나누어주어 메모리 범위를 초과하지 않도록 하였다.

 

 

www.acmicpc.net/problem/11051

11051번: 이항 계수 2