백준 2225 C++ - 합분해

Intro

문제해결 및 소스코드

• 단순한 dp문제로, 몇가지 예시만 나열해보면 특징이 보이는 문제였다.

• dp[i][j] : i를 j개의 정수로 만드는 경우의 수

• dp[i][j] = dp[i-1][j] + dp[i][j-1] 이 된다.

• 나올 수 있는 경우의수가 매우 크므로, 10억으로 나눈 값을 저장하고 출력한다.

#include <iostream>
#define MOD 1000000000

using namespace std;

int dp[201][201];

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

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

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

	cout << dp[n][k] % MOD;
}