[Baekjoon] 2225번 합분해.cpp

[백준] 2225번 합분해 문제 링크

DP는 풀어도 풀어도 어렵다. 조금씩 익숙해지는 것 같긴 한데 여전히 어렵다..

· 메인 아이디어

이번 문제는 '몇 개의 숫자'를 이용하여 '어떤 숫자'를 만드는 경우의 수를 표현하는 문제이다. 이를 위해 이 차원 배열을 사용하였다. dp[num][count] 형태로, num은 만들어야 하는 숫자, count는 num을 만드는 데 사용된 숫자의 수이다.

즉, dp[4][k]라면 '4 이하의 숫자 k개를 이용하여 4를 만드는 경우의 수'를 의미한다. k개의 숫자를 이용하여 4를 만드는 방법은 다음과 같다. 편의상 'n 이하의 숫자 '라는 표현은 생략하도록 하겠다.

먼저 4를 만드는 데에는 4 이하의 숫자만 사용된다. 따라서 다음의 경우들로 4를 만들 수 있다.

0 + 4
1 + 3
2 + 2
3 + 1
4 + 0

문제에서 0도 포함할 수 있다 했으므로 이에 유의한다. 위의 다섯 가지 경우에서 덧셈 기호의 좌측 숫자는 'k - 1개의 숫자로 만들어진 숫자'이고, 덧셈 기호의 우측 숫자는 새롭게 더할 1개의 숫자이다. 즉, 덧셈 기호의 좌우측 숫자들은 총 k개의 수로 표현된 것이다.

즉, 각 경우의 수를 모두 더한 값이 'k개의 숫자로 n'을 만드는 경우의 수가 된다. 이 내용을 바탕으로 k개의 숫자로 n을 만드는 경우의 수를 구하기 위해 다음과 같은 로직이 필요하다.

• n을 만드는 경우의 수를 만들기 위해선 0부터 n - 1까지를 만드는 경우의 수를 모두 구한다.
• k개의 숫자로 특정 수 temp를 만드는 경우의 수는
  (k-1개로 0을 만드는 경우의 수) ~ (k-1개로 temp를 만드는 경우의 수)의 합이다.

이를 구현한 소스 코드 전문은 다음과 같다.

#include <iostream>

int n, k;
long long dp[201][201] = { 0, };

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

	std::cin >> n >> k;

	for (int count = 0; count <= n; count++) {
		dp[count][1] += 1;
		for (int numCnt = 1; numCnt < k; numCnt++) {
			for (int temp = 0; temp <= count; temp++) {
				if (dp[count - temp][numCnt] > 0) {
					dp[count][numCnt + 1] = (dp[count][numCnt + 1] + dp[count - temp][numCnt]) % 1000000000;
				}
			}
		}
	}

	std::cout << dp[n][k];
}