[벡준][2225번][DP] 합분해

합분해

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

<코드>

#include <stdio.h>
#define mod 1000000000
int main(void){
 
    int N, K;
    int Dp[210][210] = {};
    scanf("%d %d", &N, &K);
 
    for (int i = 0; i <= N; i++)
        Dp[1][i] = 1;
    
    for (int i = 0; i <= N; i++)
        Dp[2][i] = i + 1;
 
    for (int i = 3; i <= K; i++)
    {
        for (int j = 0; j <= N; j++)
            for (int k = 0; k <= j; k++){
                Dp[i][j] = (Dp[i][j]+Dp[i - 1][j - k])%mod;
 
            }
        
    }
 
    printf("%d\n", Dp[K][N]%mod);
}

<문제 푼 요령>

1. 이 문제의 요령은 싶게 생각하기 힘든데 간단히 생각하자면 그 상태의 값을 구하기위해서 그 전의 값들을 전부다 구해서 더하는 식으로 구할 수 있다. 

2. 예를 들어 20을 3번의 합으로 구하는 경우의 수는 0~20을 두번의 합으로 만들 수 있는 경우의 수를 전부 더하면 되는 것이다. 

3. 이 문제는 생각하기가 어렵지 생각하고 나면 코드 구성이 어렵지 않다.