[백준] 2225번: 합분해 -JAVA

문제 바로 가기 > 2225번: 합분해

 

다이나믹 프로그래밍을 풀 수 있는 문제이다.

알고리즘 풀이

만약 입력에 예제처럼 6, 4가 주어졌다면

6= 0(3번 더해서 0이 되는 경우) + 6
6= 1 (3번 더해서 1이 되는 경우) + 5
6= 2 (3번 더해서 2가 되는 경우) + 4
6= 3 (3번 더해서 3이 되는 경우) + 3
6= 4 (3번 더해서 4가 되는 경우) + 2
6= 5 (3번 더해서 5가 되는 경우) + 1
6= 6 (3번 더해서 6이 되는 경우) + 0

 

따라서 

dp[K][N]: N이하의 정수를 K번 더해서 합이 N이 되는 경우의 수

라고 한다면 위의 경우에는 다음과 같이 표현할 수 있다.

 

dp[4][6]=dp[3][0]+dp[3][1]+dp[3][2]+dp[3][3]+dp[3][4]+dp[3][5]+dp[3][6];

 

이를 일반화한다면

dp[K][N]=dp[K-1][0]+dp[K-1][1]+dp[K-1][2]+...+dp[K-1][N-1]+dp[K-1][N]

 

이때

dp[K-1][0]+dp[K-1][1]+dp[K-1][2]+...+dp[K-1][N-1]=dp[K][N-1]이다.

따라서 dp[K][N]=dp[K][N-1]+dp[K-1][N]

 

전체 코드

import java.util.*;
import java.io.*;

public class _2225 {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken()); //최대수
        int k=Integer.parseInt(st.nextToken()); //가지수
        long DIV_NUM=1000000000;

        long max=0;
        long[][] dp=new long[k+1][n+1];
        for(int i=1;i<=k;i++){
            dp[i][0]=1;
        }

        for(int i=1;i<=k;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%DIV_NUM;
            }
        }

        System.out.println(dp[k][n]);

    }
}