백준 2225번) 합분해 java

분석

---

- 몇개(k)의 정수를 더하든 결국 마지막은 0~N이 된다.

  ex) 7 6 

        : (~, 7)(~, 6)(~, 5)(~, 4)(~, 3)(~, 2)(~, 1)(~, 0)

  하지만 마지막에 N으로 끝나는 경우는 어차피 앞부분이 0이므로 +1만 해주면 된다.

  k가 1이 아닌이상 뒤의 숫자는 무!조!건! 0~N이다 ..! 

  

  이 방법으로 문제를 접근하면 

  dp[n][k] = dp[n-0][k-1] // n-0의 k-1 개 경우의 수

  dp[n][k] = dp[n-1][k-1] // n-1의 k-1 개 경우의 수

  dp[n][k] = dp[n-2][k-1] // n-2의 k-1 개 경우의 수

  dp[n][k] = dp[n-3][k-1] // n-3의 k-1 개 경우의 수

  ...

  dp[n][k] = dp[n-(n-1)][k-1] // n-(n-1)의 k-1 개 경우의 수

  dp[n][k] += 1

  로 구할 수 있다.

 

  그리고 k개 숫자의 합분해 경우의 수를 구한다고 하면 그 전 수까지는 k-1까지만 구하고 마지막에 구하려는 k개의 숫자의 

   경우의 수를 구하면 된다 !

 

코드

---

import java.util.Scanner;
import java.util.Stack;

public class main {

    static long[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int value = sc.nextInt();
        int cnt = sc.nextInt();
        dp = new long[value + 1][cnt + 1];

        for (int i = 1; i <= value; i++) {
            dp[i][1] = 1;
            for (int j = 2; j < cnt; j++) {
                for (int k = 0; k < i; k++) {
                    dp[i][j] += dp[i - k][j - 1] % 1000000000;
                }
                dp[i][j] += 1;
            }
        }

        if (cnt == 1) {
            System.out.println(dp[value][cnt]);
        } else {
            for (int i = 0; i < value; i++) {

                dp[value][cnt] += dp[value - i][cnt - 1] % 1000000000;
            }

            dp[value][cnt] += 1;
            System.out.println(dp[value][cnt] % 1000000000);
        }
    }


}