[백준저지] 2225번 : 합분해

www.acmicpc.net/problem/2225

2225번: 합분해

1. 문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제.

 

입)

20 2

 

출)

21

 

2. 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        long[][] D = new long[K+1][N+1];
        D[0][0] = 1L;
        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;
                }
            }
        }
        System.out.println(D[K][N]%1000000000);
    }
}

D[K][N] -> 0부터 N까지의 정수 K를 더해서 그 합이 N이 되는 경우의 수

D[K][N] = ∑D[K-1][N-L], 0 <= L <= N

위 점화식을 이용해서 해결.