(c++)백준 2225번: 합분해

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

2225번: 합분해

 

※점화식※

dp[i][j] : 0부터 j까지의 정수 i개를 더해서 그 합이 j가 되는 경우의 수

dp[1][0~N] = 1로 초기화 (자기자신밖에 안 되기 때문)

ex) K=2, N=2

0부터 2까지 정수 2개 더해서 그 합이 2가 되는 경우 : 0+2, 1+1, 2+0 3개

0 + 2 : 1개 더해서 0 나오는 경우 + K번째에 2

1 + 1 : 1개 더해서 1 나오는 경우 + K번째에 1

2 + 0 : 1개 더해서 2 나오는 경우 + K번째에 0

dp[K][N] = dp[K-1][0] + ··· + dp[K-1][N]

 

#include <iostream>
using namespace std;
#define D 1000000000

int N, K;
long long dp[201][201];

void DP() {
	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 k = 0; k <= j; k++) {
				dp[i][j] += dp[i - 1][k] % D;
			}
		}
	}
	cout << dp[K][N] % D << endl;
}

int main() {
	cin >> N >> K;
	DP();
	return 0;
}