백준 2225번 - 합분해

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

K개를 더해서 합이 N이 되게 하려면 점화식을 잘 생각해야 한다.

여기서 중요한 것은 1+2와 2+1이 다른 경우에 속하는 것이다.

점화식을 세우기 전에 작은 수부터 차례대로 생각해보자.

먼저 K가 0일 때는 모든 값이 0이다.

K가 1일 때는 모든 값이 1이다.

그렇다면 K가 2일 때는 어떻게 될까?

간단하게 정리해보면 다음과 같다.

1) (1개 더해서 10) + (1개 더해서 0) = 10 (10+0)

2) (1개 더해서 9 ) + (1개 더해서 1 ) = 10 (9+1)

3) (1개 더해서 8 ) + (1개 더해서 2 ) = 10 (8+2)

4) (1개 더해서 7) + (1개 더해서 3) = 10 (7+3)

5) (1개 더해서 6 ) + (1개 더해서 4 ) = 10 (6+4)

6) (1개 더해서 5 ) + (1개 더해서 5 ) = 10 (5+5)

7) (1개 더해서 4 ) + (1개 더해서 6 ) = 10 (4+6)

8) (1개 더해서 3 ) + (1개 더해서 7 ) = 10 (3+7)

9) (1개 더해서 2 ) + (1개 더해서 8) = 10 (2+8)

10) (1개 더해서 1 ) + (1개 더해서 9 ) = 10 (1+9)

11) (1개 더해서 0 ) + (1개 더해서 10 ) = 10 (0+10)

이때 1번과 11번, 2번과 10번, 3번과 9번 등은 같은 숫자를 사용하지만

위에 나와 있는 것처럼 순서가 다르면 다른 값이기 때문에 모두 포함하면 된다.

또한, 5+5와 같이 같은 숫자를 여러 번 사용해도 돼서 포함하면 된다.

위의 과정처럼 0부터 N까지 진행한다고 할 때

K번 더해서 N이 되는 점화식은 다음과 같다.

DP[K][N] = DP[K-1][0] + DP[K-1][1] + .... + DP[K-1][N]

(K번 더해서 N이 나오는 경우의 수)

 

작은 값부터 과정을 생각해서 위의 점화식대로 풀었더니

문제를 해결할 수 있었다.

마지막으로 주의할 점은 1,000,000,000로 나눠줘야 하는데

DP 타입 자체도 long타입으로 해줘야 해결 된다.

#include <iostream>
using namespace std;
 
int main(){
    
    int N,K,mod=1000000000;
    cin>>N>>K;
    
    //dp[k][n]=k개 더해서 n나오는 경우의 수
    long dp[201][201]={0};
    for(int n=0;n<=N;n++){
        dp[1][n]=1; //0,1,2,3,...N
    }
    
    for(int k=2;k<=K;k++){
        for(int n=0;n<=N;n++){
            for(int l=0;l<=n;l++){
                dp[k][n]+=dp[k-1][l];
            }
            dp[k][n]%=mod;
        }
    }
    
    cout<<dp[K][N]<<endl;
    
    return 0;
}