백준 2225 c++ 합분해

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

2225번: 합분해

---

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector < vector <unsigned long long> > dp(201, vector <unsigned long long>(201, 0));
    //2차원 배열 dp[a][b]에서 a=분해자리수 b=분해했을 때 마지막 값 dp[a][b]는 그 개수의 합
	int N, K;
	cin >> N >> K;//N=6 K=4일 경우
	dp[1][N] = 1;//1개의 분해자리수의 개수는 6 하나 이므로 dp[1][6] = 1
	for (int i = 2; i <= K; i++)
	{
		for (int j = N; j >= 0; j--)//j=6부터 0까지 반복
		{
			for (int k = 0; k <= j; k++)//dp[4][0]의 개수는 dp[3][0]~dp[3][6]의 개수를 더한 것
			{
				dp[i][k] = (dp[i][k] + dp[i - 1][j])%1000000000;
			}
		}
	}
    //출력
	int result = 0;
	for (int i = 0; i <= N; i++)
	{
		result = (result + dp[K][i])%1000000000;
	}
	cout << result;
}

---

N=6, K=4일 때

	분해식	dp[N] 개수
dp[1][6]	6	1
dp[2][6]	0+6	1
dp[2][5]	1+5	1
dp[2][4]	2+4	1
dp[2][3]	3+3	1
dp[2][2]	4+2	1
dp[2][1]	5+1	1
dp[2][0]	6+0	1
dp[3][6]	0+0+6	dp[2][6] = 1
dp[3][5]	0+1+5, 1+0+5	dp[2][6]+dp[2][5] = 2
dp[3][4]	0+2+4, 1+1+4, 2+0+4	dp[2][6]+dp[2][5]+dp[2][4]=3
...