[백준 / JAVA] 18427번 함께 블록 쌓기

문제

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

접근

문제 자체는 심플해 보인다.
학생들의 블록을 조합하여 높이가 H인 탑을 만드는 경우의 수를 계산한다.

가장 먼저 떠올릴 수 있는 것은 역시 완전 탐색.
심플하게 n번 학생이 고를 수 있는 블록의 가짓수는 m.
따라서, $m^n = 10^{50}$ 시간 초과이다.

가짓수를 줄일 방법을 떠올려보려고 했지만 떠오르지 않았고,
DP로 풀어보려고 했지만 점화식이 그려지지 않아서 풀이를 참고했다.

i번 학생이 만들 수 있는 높이 경우의 수는, i-1번 학생까지 만든 높이 경우의 수에 더한다.
i번 학생이 만드는 높이 j의 경우의 수 dp[i][j]. 선택한 블록 val. i-1번 학생까지 만든 높이 경우의 수 dp[i - 1][j].

즉, dp[i][j] += dp[i - 1][j - val]

풀이

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

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 = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) list.add(new ArrayList<>());
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                list.get(i).add(Integer.parseInt(st.nextToken()));
            }
        }
        
        int[][] dp = new int[n + 1][h + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= h; j++) {
                dp[i][j] = dp[i - 1][j];

                for (int val : list.get(i)) {
                    if (val > j) continue;

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

                dp[i][j] = dp[i][j] % 10007;
            }
        }

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

정리

아직도 DP는 어렵다.
점화식을 만들어내는 과정이 쉽지 않은데, 연습이 많이 필요하다.