[2225번] 합분해
2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
[2225번] 합분해
0부터 N까지의 정수 중 K개를 더한 값이 N이 되는 경우의 수를 구하라.
덧셈의 순서가 바뀐 경우는 다른 경우에 해당하고, 한 개의 수를 여러 번 사용 가능하다.
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력하라
만약 N = 20, K = 1 일 때, 0 ~ 20까지의 정수 중 1개를 더한 값이 20이 되는 경우의 수는 1이다.
이를 dp로 표현하기 위해 2차원 배열을 정의하면
dp[N][K] : 정수 N을 K개의 정수의 합으로 만들 수 있는 경우의 수
N = 20, K = 1
dp[0][1] = 1 -> (0)
dp[1][1] = 1 -> (1)
dp[2][1] = 1 -> (2)
...
dp[19][1] = 1 -> (19)
dp[20][1] = 1 -> (20)
N = 20, K = 2 일 때 dp[n][k]는
N = 20, K = 2
dp[0][2] = 1 -> (0, 0)
dp[1][2] = 2 -> (0, 1), (1, 0)
dp[2][2] = 3 -> (0, 2), (1, 1), (2, 0)
dp[3][2] = 4 -> (0, 3), (1, 2), (2, 1), (3, 0)
...
dp[0][2] = 1
dp[1][2] = dp[0][1] + dp[1][1]
= (dp[0][1]에 정수 하나를 더하여 1이 나오는 경우)
+ (dp[1][1]에 정수 하나를 더하여 1이 나오는 경우)
dp[2][2] = dp[0][1] + dp[1][1] + dp[2][1]
= (dp[0][1]에 정수 하나를 더하여 2가 나오는 경우)
+ (dp[1][1]에 정수 하나를 더하여 2가 나오는 경우)
+ (dp[2][1]에 정수 하나를 더하여 2가 나오는 경우)
dp[3][2] = dp[0][1] + dp[1][1] + dp[2][1] + dp[3][1]
= (dp[0][1]에 정수 하나를 더하여 3이 나오는 경우)
+ (dp[1][1]에 정수 하나를 더하여 3이 나오는 경우)
+ (dp[2][1]에 정수 하나를 더하여 3이 나오는 경우)
+ (dp[3][1]에 정수 하나를 더하여 3이 나오는 경우)
....
위처럼 dp[n][2]를 구할 수 있다.
이때, dp[2][2] = dp[1][2] + dp[2][1], dp[3][2] = dp[2][2] + dp[3][1] 으로 표현 가능하다
이를 통해 점화식을 구하면 dp[n][k] = dp[n-1][k] + dp[n][k-1] 이다.
for(int i = 0; i <= n; i++) {
for (int j = 2; j <= k; j++) {
if (i == 0) {
dp[i][j] = 1;
continue;
}
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
}
}
[전체소스코드]
#include <stdio.h>
#include <iostream>
using namespace std;
int main() {
int n = 0;
int k = 0;
int dp[201][201] = { 0 };
const int mod = 1000000000;
cin >> n >> k;
for (int i = 0; i <= n; i++) {
dp[i][1] = 1;
}
for(int i = 0; i <= n; i++) {
for (int j = 2; j <= k; j++) {
if (i == 0) {
dp[i][j] = 1;
continue;
}
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
}
}
cout << dp[n][k] << endl;
return 0;
}