[C++] 백준 2225번: 합분해

dp라는 건 금방 감이 왔고 N과 K가 만큼 더해야 하니까 2차원 배열을 써야겠다고 생각이 났다.

dp 배열에서 행은 N, 열은 K를 저장한다고 볼 때 dp[3][3]을 구해보자.

dp[1][1]=1, dp[1][2]=2, dp[1][3]=1;
dp[2][1]=1, dp[2][2]=3, dp[2][3]=4;
dp[3][1]=1, dp[3][2]=4, dp[3][3]=8;

dp[2][2]=dp[1][1]+dp[1][2]이고
dp[3][3]=dp[2][1]+dp[2][2]+dp[2][3] 임을 볼 수 있다.

 

#include<iostream>
#define MAX 1000000000

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n, k;
	cin >> n >> k;

	long long dp[201][201] = { 0, };

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

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

	cout << dp[n][k];
	return 0;
}