백준 2225번 합분해 (C++)

요새 DP에 좀 뜸한 거 같아서 DP를 풀어봤다.
하지만 고민만 늘어나게 되는데....

문제링크

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

설명

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다.
다이나믹 프로그래밍의 핵심은 어떻게든 점화식을 뽑아내는 거라고 생각한다.
그래서 점화식을 뽑아내는데 초점을 두고 문제를 푸는데 쉽지 않았다.

질문글을 보던 중 수들의 관계에 집중하라는 글을 보고 K = 1일 때, N의 경우의 수들을 차례로 적어나가던 중 관계를 발견할 수 있었다.

어때...? 나의 더러운 풀이...?

N = 6, K = 4일 때의 값은 N = 6, K = 3일 때와, N = 5이고 K = 4일 때의 합임을 알 수 있다.
이를 식으로 나타내면 DP[N][K] = DP[N][K - 1] + D[N - 1][K]이다.
반례가 없음을 확인하고 제출했더니 AC를 받을 수 있었다.

모듈러 연산을 활용해야하는 문제는 int의 범위를 초과하는 경우가 생긴다는 뜻이니 long long으로 선언하는 것을 잊지 말자.

하지만 답을 제출하고나서 의문이 생겼다...
나는 이 문제의 풀이를 논리적으로 발견한 것이 아닌 우연히 발견했다고 생각한다.
실제로 다른 블로그의 설명을 보면 결과적으로 점화식은 같지만 다른 방식으로 풀이를 설명하고 있다.
다른 고난이도의 문제에서도 점화식을 우연히 발견하는 것은 쉽지않을 것이다...
앞으로 DP문제를 풀 때는 논리적으로 점화식을 뽑아내는 것에 집중하되, 너무 많은 시간을 소비하지 않게끔 노력해야겠다.

점화식이 안 보이면 진짜 끝까지 안 보이는 경우가 너무 많아서 그냥 다른 날 푸는 게 정신 건강에 좋을 듯.

코드

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	int n, k, div = 1000000000;
	cin >> n >> k;
	vector<vector<long long>> sumdismental(n + 1, vector<long long>(k + 1, 1));

	for (int i = 2; i <= k; i++)
	{
		for (int j = 1; j <= n; j++)
			sumdismental[j][i] = (sumdismental[j - 1][i] + sumdismental[j][i - 1]) % div;
	}
	cout << sumdismental[n][k] % div;
	return 0;
}