[BOJ/2225] 합분해

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

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

 

사용 알고리즘

- DP

 

풀이

- d[k][n] = 0 ~ n 정수 k개를 더해서 합이 n이 되는 경우의 수

- d[k][n] += d[k - 1][n - l] (0 <= l <= n)

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/2225.cpp

#include <cstdio>
 
int d[203][203];
 
int main(void) {
    int n, k; scanf("%d %d", &n, &k);
    d[0][0] = 1;
    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;
            }
        }
    }
    printf("%d\n", d[k][n]);
    return 0;
}