[Baekjoon] 2655번 : 가장 높은 탑 쌓기

1. 문제

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

• DP, LIS 문제

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

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

// 입력
첫째 줄에는 입력될 벽돌의 수가 주어진다.
입력으로 주어지는 벽돌의 수는 최대 100개이다.
둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이,
벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다.
각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다.
벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.

// 출력
탑을 쌓을 때 사용된 벽돌의 수를 빈칸없이 출력하고,
두 번째 줄부터는 탑의 가장 위 벽돌부터 가장 아래 벽돌까지
차례로 한 줄에 하나씩 벽돌 번호를 빈칸없이 출력한다.

// 예제 입력 1
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

// 예제 출력 1
3
5
3
1

2. 핵심 아이디어

• 가장 긴 증가하는 부분 수열 문제의 심화 변형 문제
• 벽돌의 수가 N개일 때, 시간 복잡도 O(N^2)으로 해결할 수 있음
• 벽돌의 번호를 출력해야 한다는 점에서, 계산된 테이블을 역추적할 수 있어야 함
• 가장 먼저 벽돌을 무게 기준으로 정렬
• D(i) = 인덱스가 i인 벽돌을 가장 아래에 두었을 때의 최대 높이
• 각 벽돌에 대해서 확인하며 D(i)를 갱신
• 모든 0 <= j < i 에 대하여, D(i) = max(D(i), D(j) + height(i) if area(i) > area(j))

3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = []

arr.append((0, 0, 0, 0))

for i in range(1, n + 1) :
  area, height, weight = map(int, input().split())
  arr.append((i, area, height, weight))

# 무게 기준 정렬
arr.sort(key = lambda data: data[3])

dp = [0] * (n + 1)

for i in range(1, n + 1) :
  for j in range(0, i) :
    if arr[i][1] > arr[j][1] :
      dp[i] = max(dp[i], dp[j] + arr[i][2])

max_value = max(dp)
index = n
result = []

while index != 0 :
  if max_value == dp[index] :
    result.append(arr[index][0])
    max_value -= arr[index][2]
  index -= 1

result.reverse()
print(len(result))
[print(i) for i in result]

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

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

    int n = Integer.parseInt(br.readLine());
    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]);
      }
    });

    int[] dp = new int[n + 1];

    for (int i=1; i<n+1; i++) {
      for (int j=0; j<i; j++) {
        if (arr[i][1] > arr[j][1]) {
          dp[i] = Math.max(dp[i], dp[j] + arr[i][2]);
        }
      }
    }

    int max_value = 0;
    for (int i : dp) {
      max_value = Math.max(i, max_value);
    }

    int index = n;
    ArrayList<Integer> result = new ArrayList<Integer>();

    while (index != 0) {
      if (max_value == dp[index]) {
        result.add(arr[index][0]);
        max_value -= arr[index][2];
      }
      index--;
    }
    System.out.println(result.size());

    for (int i=result.size()-1; i>=0; i--) {
      System.out.println(result.get(i));
    }
  }
}