[백준] 2655번. 가장높은탑쌓기(JAVA)

문제

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

---

풀이(40분)

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

public class Main {
    static int N;
    static int[][] blocks; // [i][0]: 밑면 넓이, [1]: 높이, [2]: 무게
    static Info[] dp;

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

        blocks = new int[N + 1][3];
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                blocks[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp = new Info[N + 1];
        Info result = new Info(0, "");

        // 모든 블록을 위에 둘 수 있는 경우를 탐색
        for (int i = 1; i <= N; i++) {
            Info candidate = buildTower(i);
            if (candidate.height > result.height) {
                result = candidate;
            }
        }

        // 결과 문자열 처리 (쌓은 블록 번호를 역순 출력)
        String[] usedBlocks = result.order.trim().split(" ");
        StringBuilder sb = new StringBuilder();
        sb.append(usedBlocks.length).append("\n");
        for (int i = usedBlocks.length - 1; i >= 0; i--) {
            sb.append(usedBlocks[i]).append("\n");
        }

        System.out.print(sb);
    }

    // 특정 블록을 가장 위에 둘 때 최대 높이와 블록 순서를 반환
    static Info buildTower(int top) {
        if (dp[top] != null) return dp[top];

        int maxHeight = blocks[top][1];
        String towerOrder = "";

        for (int below = 1; below <= N; below++) {
            if (blocks[below][0] < blocks[top][0] && blocks[below][2] < blocks[top][2]) {
                Info belowInfo = buildTower(below);
                int candidateHeight = blocks[top][1] + belowInfo.height;

                if (candidateHeight > maxHeight) {
                    maxHeight = candidateHeight;
                    towerOrder = belowInfo.order;
                }
            }
        }

        dp[top] = new Info(maxHeight, top + " " + towerOrder);
        return dp[top];
    }

    // 블록을 쌓은 결과를 저장하는 클래스: 높이와 블록 순서
    static class Info {
        int height;
        String order;

        Info(int height, String order) {
            this.height = height;
            this.order = order;
        }
    }
}

---

문제 풀이 전략

 

중요 포인트는 아래에서 위로 쌓아가는 게 아닌 위에서 아래로 쌓는 방식으로 생각을 하는 것이다.

 

또한, dp를 활용해 이전에 탐색했던 블록에 대한 정보가 있다면 이를 재활용하게 하여 최적화한다.