[BOJ] 2225 합분해

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

 

 

문제 풀이:

 

예제를 통해 규칙성을 찾아보자

위 예제를 통해 점화식이 다음과 같이 세울 수 있다 

* dp[k][n]: 정수 k개를 사용해서 n을 만든 경우 수 

점화식 → dp[k][n]= dp[k-1][0]+dp[k-1][1]+ ... +dp[k-1][n]  = $\sum_{i=0}^{n}dp[k-1][i]$

 

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;
ll n, k, dp[202][202];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;

	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 z = 0; z <= j; z++) {
				dp[i][j] += dp[i - 1][z];
				dp[i][j] %= 1000000000;
			}
		}
	}
	cout << dp[k][n] << '\n';
	return 0;
}

 

하지만, 조금 더 생각해보면 2중 포문만으로도 문제를 풀 수 있다. 

dp[n][k]= $\sum_{i=0}^{n}dp[k-1][i]$이므로

각 k마다 k-1에 대해 나올 수 있는 값들의 합을 넘겨주면 된다.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;
ll n, k, dp[202];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;
	for (int i = 0; i <= n; i++) dp[i] = 1;
	
	for (int i = 1; i < k; i++) {
		for (int j = 1; j <= n; j++) {
			dp[j] += dp[j - 1];
			dp[j] %= 1000000000;
		}
	}
	cout << dp[n] << '\n';
	return 0;
}