백준 2225번 C++ 합분해

합분해

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

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

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

생각하는 과정

아직도 dp를 잘 못 이해하고 있었던 건지 ㅠㅠ 이상하게 풀려고 했었다.

끄적거리다가 맥도날드가 시끄러워서 견딜 수 없게 되었을 즈음 이렇게 하면 되는구나 생각이 났다.

예를 들어, 0부터 5까지의 정수 4개를 이용하여 5를 만든다고 해보자.

그러면 처음에는

1000

0100

0010

0001

로 시작할 수 있다.

이 네 개를 단위벡터 단위행렬... 처럼 하나의 단위로 생각하고 2번째도 구하면 된다.

1000+1000=2000

1000+0100=1100

1000+0010=1010

1000+0001=1001

이런 식으로.

그런데 0100부터는

0100+1000=1100

이므로 중복이 생겨버린다.

따라서 자기 자신과 일치하는 것부터 더해주면 되는 것이다.

이런식으로 다음은 4+3+2+1=10

1차원 배열로 풀려다가 그 전항 정보도 알아야 하고 이 쪽이 직관적이어서 2차원 배열을 택했다...

아무튼 dp[2][1]=4, dp[2][2]=3, dp[2][3]=2, dp[2][4]=1을 저장해준다.

이런 식으로 반복하면 다음의 코드가 나온다.

3번째도 마찬가지로

dp[3][1]=dp[2][1]+dp[2][2]+dp[2][3]+dp[2][4]

dp[3][2]=dp[2][2]+dp[2][3]+dp[2][4]

dp[3][3]=dp[2][3]+dp[2][4]

dp[3][4]=dp[2][4]

이렇게 반복될 수 있는 이유는, n번째의 합은 n-1번째+1번째이기 때문이다.

따라서 1, 2, 3, 4번째를 차례대로 더해주면 답을 구할 수 있는 것이다.

코드

#include <iostream>
#define MOD 1000000000
using namespace std;
int main() {
    int N, K;
    cin>>N>>K;
    if(K==1) {
        cout<<1<<endl;
        return 0;
    }
    int sum=0, dp[201][201]={0,};
    for(int i=0; i<K; i++) {
        dp[1][i]=1;
    }
    for(int i=2; i<=N; i++) {
        for(int j=0; j<K; j++) {
            for(int k=j; k<K; k++) {
                dp[i][j]+=dp[i-1][k]%MOD;
                dp[i][j]%=MOD;
            }
        }
    }
    for(int i=0; i<K; i++) {
        sum+=dp[N][i];
        sum%=MOD;
    }
    cout<<sum<<endl;
    return 0;
}