21.07.16 - [BOJ] 2225. 합분해

[suhyunsim]

문제

• 2225

핵심 아이디어

• D[K][N] = 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수
  • = ΣD[K-1][N-L] (0 ≤ L ≤ N)
• 1개 풀 때 O(N) -> 전체 문제는 KN개 -> O(KN^2)
• 수 아무것도 사용하지 않았을 때 D[0][0] = 1

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q2225;

import java.util.Scanner;

public class Main {
    static long MOD = 1000000000L;
    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] = 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] %= MOD;
                }
            }
        }
        System.out.println(d[k][n]);
    }
}