백준 2225 / 합분해

다이나믹 프로그래밍 문제

이것도 어렵다.

d[k][n]이 k개의 수로 n을 완성한 경우의 수라고 하자.

ㅇ+ ㅇ + ..... + ㅇ + ㅇ = n

(ㅇ의 개수가 k)

여기서 마지막 ㅇ를 L라고 가정했을때 점화식은

d[k][n] = 시그마(d[k-1][n-L]) 

항상 점화식을 세울때 변수의 범위를 생각하여야 한다.

여기서 변수는 L이므로 L의 범위는 0<= L <= n

코드는

#include <stdio.h>
#include <iostream>
#include <math.h>
 
using namespace std;
 
int main() {
 
    int d[201][201];
 
    for (int i = 0; i < 201; i++) {
        for (int j = 0; j < 201; j++) {
            d[i][j] = 0;
        }
    }
 
    int n, k;
    cin >> n >> k;
 
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            for (int l = 0; l <= j; l++) {
                d[i][j] += d[i - 1][j - l];
                d[i][j] %= 1000000000;
            }
        }
    }
    cout << d[k][n];
 
}