[BOJ] 2225 :: 합분해

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

다이나믹 프로그래밍으로 해결했습니다.

아무리 생각해도 1차원 dp로는 해결되지 않는데 아직 2차원 dp에 약한지 점화식 세우는데 꽤 애를 먹었네요 ㅠ

우선 dp[202][202]정도 잡아줍니다

이 때 dp[k][n]의 정의는 k번 더해서 n을 만들 수 있는 경우의 수 입니다.

dp[i][n] 은 dp[i-1]행에서 0부터 n까지 값을 더해서 만들 수 있습니다.

i-1번 더해서 만들 수 있는 경우의 수에 0부터 n까지 어떤 수던 한개 더하면 n을 만들 수 있으니까요!

5 by 5의 예를 들어 보겠습니다.

   0 1 2 3 4 5

1 1 1 1 1 1 1

2 1 2 3 4 5 6

3 1 3 6 10 15 21

4 1 4 10 20 35 56

5 1 5 15 35 55 91

이렇게 계산해서 우리가 구하고자 하는 값 dp[k][n]을 구하면 됩니다.

그리고 mod연산이 필요한데 dp를 구할 때마다 mod연산을 해주여야 오답이 나오지 않습니다.

저처럼 마지막 답 낼때만 mod연산 하시면 안됩니다...그전에 overflow가 나서 이상한 값으로 업데이트 되는 경우가 생기더라구요.

#include <iostream>
using namespace std;
long long dp[202][202];
int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i <= n; i++)
	{
		dp[1][i] = 1;
	}//초기값 설정
	for (int i = 2; i <= k; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			for (int l = 0; l <= j; l++)
			{
				dp[i][j] += dp[i - 1][l];
				dp[i][j] %= 1000000000;
			}
		}
	}
	long long ans = dp[k][n];
	cout << ans % 1000000000<< endl;
}