[Baekjoon] 2225번 합분해.cpp
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];
}
Author And Source
이 문제에 관하여([Baekjoon] 2225번 합분해.cpp), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cedongne/Baekjoon-2225번-합분해.cpp저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)