[백준 C++] 2225번: 합분해

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

 

dp마지막 문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구해야 한다.

 

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

 

n이 1부터 200까지 k도 1부터 200까지 dp[201][201]로 만들어서 풀어야할것같은 예감이 든다.

 

아예 표를 만들어보자

	k=1	k=2	k=3	k=4
n=1	1	2	3	4
n=2	1	3	6	10
n=3	1	4	10	20
n=4	1	5	15	35

 

       

n과 k는

 

즉, dp[n][k]는 dp[n-1][k] + dp[n][k-1]로 구할 수 있다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[201][201] = { 0, };
 
int main(int argc, char* argv[])
{
    int n, k;
    cin >> n >> k;
 
    for (int i = 0;i <= k;i++)
        dp[1][i] = i;
 
    for (int i = 2;i <= n;i++)
        for (int j = 1;j <= k;j++)
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000;
    
    cout << dp[n][k];
 
    return 0;
}

 

규칙만 찾는다면 dp문제는 어렵지 않게 풀 수 있지만 그 규칙을 모른다면 시간이 아무리 많이 주어져도 풀기 힘든 문제라고 생각한다.

 

이문제 또한 표를 그려보지 않았다면 규칙을 찾아내기 힘든 문제였다.

 

여러 문제를 풀어봐야겠다.