[Java]BOJ 2225 : 합분해

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

🚩문제

🔓문제해결

N까지의 정수를 0개 더해서 그 합이 0이 되는 경우의 수 0을 k번 더하는 방법 1개밖에 없다.

k=1일 경우 N까지의 정수를 1개 더해서 그 합이 N이 되는 경우의 수

=> 자기 자신만 가짐. 1개

=> dp[k+1][n+1] 의 크기일 경우 dp[1]을 1로 채워준다.

1. N=1일때
   1. k=1 : 1               :: 1가지
   2. k=2 : 1+0 , 0+1  :: 2가지
   3. k=3 : 1+0+0 , 0+1+0, 0+0+1 :: 3가지  
2. N=2 일때
   1. k=1 : 2               :: 1가지
   2. k=2 : 2+0 , 0+2,1+1  :: 3가지
   3. k=3 : 1+1+0 , 1+0+1, 0+1+1 ,2+0+0,0+2+0,0+0+2 :: 6가지
3. N=3 일때
   1. k=1 : 3               :: 1가지
   2. k=2 : 3+0 ,0+3,1+2,2+1  :: 4가지
   3. k=3 : 1+1+1,1+2+0,2+1+0,1+0+2, 2+0+1, 0+1+2, 0+2+1, 3+0+0, 0+3+0, 0+0+3 :: 10가지

 

k    \      n	0	1	2	3
1	dp[1][0] = 1	dp[1][1] = 1	dp[1][2] = 1	dp[1][3] = 1
2	dp[2][0] = 1	dp[2][1] = dp[2][0]+dp[1][1]  =dp[1][0]+dp[1][1]	dp[2][2] =dp[2][1]+dp[1][2]	dp[2][3] =dp[2][2]+dp[1][3]
3	dp[3][0] = 1	dp[3][1] = dp[3][0]+[2][1]	dp[3][2] =dp[3][1] +dp[2][2]	dp[3][3] =dp[3][2]+d[2][3]

import java.util.Arrays;
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int mod = 1000000000; //나눠서 출력해야하는수를 변수로 지정해줌
        int n= sc.nextInt();
        int k= sc.nextInt();
        int [][]dp= new int[k+1][n+1]; //범위가 0부터 시작
        Arrays.fill(dp[1], 1); //k=1인경우 자기자신뿐임
        for (int i = 1; i <= k; i++) dp[i][0] = 1; //0만 계속 더해지므로 경우의 수 1개
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod;
            }
        }
        System.out.println(dp[k][n]);

    }

}