(C++) 백준 2225 합분해

문제 및 풀이

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

• 0개 더해서 i가 되는 경우의 수는 1가지!
• 1개 더해서 i가 되는 경우의 수는 1가지
• 2개 더해서 i가 되는 경우의 수
  • 1개 더해서 i-1 되는 수 + 1 == 2개 더해서 i되는 수
  • 1개 더해서 i-2 되는 수 + 2 == 2개 더해서 i되는 수
  • 1개 더해서 i-3 되는 수 + 3 == 2개 더해서 i되는 수
  • .....
  • 1개 더해서 i되는 수 + 0 == 2개 더해서 i되는 수

즉, 이를 일반화하면 k개 더해서 n이 되는 수 dp[k][n]는
dp[k][n] = dp[k-1][0] +....... dp[k-1][n]

코드

#include <iostream>
#define ll long long
using namespace std;

const ll MOD = 1000000000;
ll dp[205][205];

int main(){


    int N,K; cin>>N>>K;

    for(int i=0; i<=N; i++) dp[1][i]=1; 

    for(int k=2; k<=K; k++) {
        for(int x=0; x<=N; x++){
            for(int i=0; i<=x; i++){
                dp[k][x] += dp[k-1][i];
                if(dp[k][x]>MOD) dp[k][x]-=MOD;
            }

        }
    }

    cout<<dp[K][N];

}