[BOJ] 2225 - 합분해

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

---

[알고리즘풀이]

Dp[i][j] : 숫자 j 를 i 개의 숫자로 표현할 수 있는 경우의 수.

그럼 다음과 같은 방정식이 성립한다.

Dp[i][j] = Dp[1][j - 1] + Dp[2][j - 1] + ⋯ + Dp[i][j-1]

#include<iostream>

using namespace std;

#define m 1000000000;
int dp[201][201];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, k;
	cin >> n >> k;
	for (int j = 0; j <= n; j++)
		dp[1][j] = 1;
	for (int j = 0; j <= k; j++)
		dp[j][0] = 1;

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

---