백준 2225번 합분해 C++

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

다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

dp테이블을 dp[n][k]라고 하고, k개의 수로 n을 만들 수 있는 경우의 수 라고 하였다.

 

의외로 간단하게 해결할 수 있다.

예를 들어 dp[3][4]는 4개의 수로 3을 만들 수 있는 경우의 수인데,

마지막에 0이 온다면 3개의 수로 3를 만드는 경우의 수,

마지막에 1이 온다면 3개의 수로 2을 만드는 경우의 수,

마지막에 2가 온다면 3개의 수로 1를 만드는 경우의 수,

마지막에 3이 온다면 3개의 수로 0을 만드는 경우의 수 이다.

이 경우들을 모두 합하면 되기 때문에 점화식은 dp[n][k] = dp[n][k-1] + dp[n-1][k-1] + dp[n-2][k-1] + .... dp[0][k-1] 이다.

그리고 테이블을 채워가다 보면 dp[n-1][k-1] + dp[n-2][k-1] + .... dp[0][k-1] 은 dp[n-1][k]와 같다는 것을 알 수 있다.

그러므로 최종 점화식은 dp[n][k] = dp[n][k-1] + dp[n-1][k] 이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	vector<vector<ll>> dp(201, vector<ll>(201, 1));
	int n, k;
	cin >> n >> k;
	for (int i = 1; i < 201; i++) {
		for (int j = 2; j < 201; j++) {
			dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
			dp[i][j] %= 1000000000;
		}
	}
	cout << dp[n][k] % 1000000000;
};