[Java] 백준 2655 가장높은탑쌓기

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

문제

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
벽돌들의 높이는 같을 수도 있다.
탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

풀이

1. 벽돌 정보 저장

• 벽돌의 입력 정보인 (번호, 밑면 넓이, 높이, 무게)를 배열에 저장합니다.
• 번호를 저장하는 이유: 정렬 후에도 원래 벽돌의 순서를 유지하기 위해

2. 벽돌 정렬

• 벽돌을 무게 기준으로 오름차순 정렬
  (무거운 벽돌을 가벼운 벽돌 위에 올릴 수 없기 때문에 정렬 필요)

3. LIS(최장 증가 부분 수열) 방식으로 dp 테이블 계산

• dp[i]는 벽돌 i를 가장 아래에 두었을 때 만들 수 있는 최대 높이입니다.

• j < i를 탐색하면서 넓이 조건을 만족하는 경우

  	-> dp[i] = max(dp[i], dp[j] + height[i])로 갱신

4. 최대 높이를 만드는 벽돌 찾기

• dp 배열에서 가장 높은 값을 찾고, 해당 벽돌부터 역추적하여 사용된 벽돌 번호 저장
• maxHeight -= 현재 벽돌의 높이를 하면서 어떤 벽돌이 포함되었는지 확인

5. 출력

• 사용된 벽돌의 개수와
• 사용된 벽돌 번호를 위에서 아래 순서대로 출력

정답코드

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));

        // 벽돌의 개수
        int n = Integer.parseInt(br.readLine());

        // 1 based
        // arr[i] = {벽돌 번호, 밑면 넓이, 높이, 무게}

        int[][] arr = new int[n + 1][4];

        // 벽돌 정보 입력 받기
        for (int i = 1; i < n + 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = i;
            arr[i][1] = Integer.parseInt(st.nextToken()); // 밑면 넓이
            arr[i][2] = Integer.parseInt(st.nextToken()); // 높이
            arr[i][3] = Integer.parseInt(st.nextToken()); // 무게
        }


        // "무게" 기준으로 오름차순 정렬(가벼운 벽돌을 위에 쌓음)
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[3], o2[3]); // 무게 기준 정렬
            }
        });

        // 1. dp 테이블 생성
        // i번째 벽돌을 가장 아래에 두었을때 만드는 최대 높이
        int[] dp = new int[n + 1];

        // 2. 점화식
        // LIS(최장 증가 부분 수열)로 dp 테이블 갱신
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < i; j++) {
                // j번째 벽돌의 밑 넓이가 i번째 벽돌의 밑 넓이보다 작아야 위에 올림
                if (arr[i][1] > arr[j][1]) {
                    // j번째 벽돌을 아래에 두고, 벽돌을 추가한 높이 / 기존 높이 중 큰 값 선택
                    dp[i] = Math.max(dp[i], dp[j] + arr[i][2]);
                }
            }
        }

        // dp 배열 중 가장 높은 값 찾기(탑 최대 높이)
        int max_val = 0;
        for (int i : dp) {
            max_val = Math.max(i, max_val);
        }

        int idx = n;
        ArrayList<Integer> ans = new ArrayList<Integer>();

        while (idx != 0) {
            if (max_val == dp[idx]) { // 최대 높이 = 현재 벽돌 높이
                ans.add(arr[idx][0]); // 벽돌 번호
                max_val -= arr[idx][2]; // 현재 벽돌 높이만큼 줄이기
            }
            idx--;
        }

        // 사용된 벽돌 개수
        System.out.println(ans.size());

        // 사용된 벽돌 번호를 위->아래로 출력
        for (int i = ans.size() - 1; i >= 0; i--) {
            System.out.println(ans.get(i));
        }
    }
}

참고한 블로그
https://leewonwoo1.github.io/baekjoon/cs-baekjoon-2655/