[백준 2225 - C++] 합분해 : DP

www.acmicpc.net/problem/2225

2225번: 합분해

문제

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

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

 

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

 

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

예제 입력 1 

20 2

예제 출력 1 

21

 

풀이

위의 식처럼 N을 k개로 나타내는 방법의 수는 k-1개로 N~0을 나타내는 방법의 수를 모두 합친 것과 같다!

왜내면 각각에 0~N을 더해주면 N이 되니까!

간단한 문제이다. DP는 언제나 느끼지만 풀이 방법을 생각해내기만 하면 참 쉽게 풀린다...

 

#include <iostream>
#include <cstdio>

int dp[201][201];

int main(void){
    int n, k;
    scanf("%d %d", &n, &k);
    for(int j=1; j<k+1; j++){
        dp[0][j] = 1;
    }
    for(int i=1; i<n+1; i++){
        dp[i][1] = 1;
    }
    
    for(int i=1; i<n+1; i++){
        for(int j=2; j<k+1; j++){
            for(int k=0; k<i+1; k++){
                dp[i][j] = (dp[i][j] + dp[i-k][j-1]) %  1000000000;
            }
        }
    }
    printf("%d\n", dp[n][k]% 1000000000);
}