[BOJ] 2225 : 합분해 - travelbeeee

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

---

[ 알고리즘풀이 ]

 2차원 배열을 활용해야되는 DP(다이나믹 프로그래밍)문제입니다.

'DP[x][y] = 정수 y개의 합이 x가 되는 모든 경우의 수' 라고 정의하면 다음과 같은 식이 성립합니다.

1. DP[1][y] = y , for 1 <= y <= 200

2. DP[x][1] = 1 , for 1 <= x <= 200

3. DP[x][y] = DP[x -1][y] + DP[x][y - 1], for 2 <= x <= 200 && 2 <= y <= 200

#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 = 1; j <= 200; j++)
		dp[1][j] = j;
	for (int i = 1; i <= 200; i++)
		dp[i][1] = 1;
	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]) % m;

	cout << dp[N][K];
}

---