[Algorithm] 백준 DP문제 - 합분해(2225) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP문제 - 합분해 자바 풀이를 진행하도록 하겠습니다.

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

2225번: 합분해

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());
        
        SumDivision sd = new SumDivision(n, k);
        sd.run();
    }
}

class SumDivision {
    
    static final int MOD = 1000000000;
    int n;
    int k;
    int[][] dp;

    SumDivision(int n, int k) {
        this.n = n;
        this.k = k;
        dp = new int[k + 1][n + 1]; // i 개로 총 합이 j을 만드는 것        
    }
    
    void run() {

        Arrays.fill(dp[1], 1); // i = 1, 즉 1개로 j의 값을 만드는 경우는 한 개
        for (int i = 1; i <= k; i++) dp[i][0] = 1; // 총 합이 0이 되도록 만드는 경우는 각 개수 별로 한 개씩 
        // ex) i = 1, 합이 0 ==> 0 (한 개 존재)
        // ex) i = 2, 합이 0 ==> 0 + 0 (한 개 존재)

        // dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + .... + dp[i - 1][j];
        //   j
        // = sum(dp[a - 1][b]) 
        //   b -> 0 

        //   j - 1
        // = sum(dp[a - 1][b]) + dp[i - 1][j]
        //   b -> 0

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

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

 

2. 풀이 중점 사항

 

이번 문제는 점화식을 도출하는 과정이 많이 어려웠습니다.

정수 K개를 더해서 N까지의 합을 어떻게 만들어야 하는가가 핵심이었습니다.

 

하나의 예시를 살펴보겠습니다.

N을 만들기 위해서는 합이 0 ~ n 이 되도록 k - 1개를 사용하여야 합니다.

즉, N이 3이라면

k = 2일 때, preSum = 0, 1, 2, 3 이 완성되어야 합니다.

 

k = 3이라면,

preSum = 0     +      3 (현재)

preSum = 1     +      2 (현재)

preSum = 2     +      1 (현재)

preSum = 3     +      0 (현재)

 

를 구할 수 있습니다. 이를 수학적으로 표현하면 다음과 같습니다.

DP[a][b]가 a개를 사용하여 값이 b를 만드는 경우의 수라고 한다면,

 

DP[k][N] =  DP[k - 1][0] + DP[k - 1][1] +    ...   + DP[k - 1][N] 으로 표현할 수 있습니다.

하단에 참조 블로그의 블로거 분께서 점화식을 도출해주셨는데, 참고하면 다음과 같습니다.

 

 

시그마의 성질로 인해 마지막 항을 따로 분리하면, dp[K - 1][N]이 되고, 시그마를 정리하면 dp[k][N - 1]이 되므로 두 항을 더하면

하나의 점화식을 완성 시킬 수 있습니다.

 

dp[i][j] = dp[i][j - 1] + dp[i - 1][j];

 

이때, k = 1으로 N을 만드는 경우의 수는 자기 자신을 더하는 것밖에 없으므로 

dp[1][all] = 1 을 처리해주어야 합니다. 또한, k개로 0을 만드는 경우도 마찬가지로 1 개입니다.

 

ex) k = 1 -> 0

      k = 2 -> 0 + 0

 

따라서, 이 경우들을 제외하고는 위의 점화식을 적용시키면 문제를 해결할 수 있습니다.

이상으로 백준 합분해 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

 

참고 자료: https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-2225-%EC%9E%90%EB%B0%94-%ED%95%A9%EB%B6%84%ED%95%B4-BOJ-2225-JAVA