[BOJ] 백준 2225 합분해 (JAVA)

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

2225번: 합분해

🔎 Solve

다이나믹 프로그래밍(DP)을 이용하여 풀었습니다.

해당 문제를 표를 만들어서 생각해보면 점화식을 쉽게 만들어낼 수 있습니다.

 

문제에서 예제 입력 2번과 같이 N=6, K=4일 때를 예로 들어보겠습니다.

2차원 int형 배열을 만들어서 

행에는 K (1~4)를, 열에는 N (0~ 6)을 나타내는 배열을 만들어줍니다.

 

dp	0	1	2	3	4	5	6
1
2
3
4

 

해당 dp.배열을 K개의 숫자로 N을 만들 수 있는 경우의 수를 채워줍니다.

이때, K가 1개일 때는 각 숫자 자신만이 가능하니 1로 채워줍니다.

N가 0일 땐 0 자신만 가능하므로 마찬가지로 1로 채웁니다.

 

dp	0	1	2	3	4	5	6
1	1	1	1	1	1	1	1
2	1
3	1
4	1

 

다음으로 (2, 1)을 살펴보면, 

숫자 1개로 1을 만들 수 있는 경우의 수(1+0) + 2개의 숫자로 0을 만들 수 있는 경우의 수를 더해주면(0+1) 

숫자 2개로 1을 만들 수 있는 경우의 수를 구할 수 있습니다.

같은 방식으로 표를 채웁니다.

 

dp	0	1	2	3	4	5	6
1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7
3	1	3	6	10	15	21	28
4	1	4	10	20	35	56	84

 

따라서 dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j-1 ]와 같은 점화식을 세울 수 있습니다.

 

위와 같은 예제에선 dp[4][6]의 값이 84이므로, 문제에서 주어진 것과 같이 1000,000,000를 나눈 답을 출력합니다.

 

🐱‍💻 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, K;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        dp = new int[K+1][N+1];

        for(int n=0;n<=N;n++){
            dp[1][n] = 1;
        }

        for(int k=1;k<=K;k++){
            dp[k][0] = 1;
        }

        for(int k=2;k<=K;k++){
            for(int n=1;n<=N;n++){
                dp[k][n] = dp[k-1][n] + dp[k][n-1];
                dp[k][n] %=1000000000;
            }
        }

        System.out.println(dp[K][N]);

    }
}