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

문제 링크

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

문제

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

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

입력

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

출력

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

풀이

벽돌을 가장 높게 쌓아야 한다.

모든 경우의 수는 100!이기 때문에 완탐은 불가능하고, 쌓기 위한 기준이 넓이와 무게이기 때문에 최선의 선택이 없어 그리디도 아니다.

dp를 활용하는 문제인데 예제 입력 1로 풀이해 보겠다.

5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

최선의 선택은 없기 때문에 첫 번째로 쌓을 수 있는 벽돌은 5가지가 된다.

25 3 4를 먼저 쌓았다고 했을 때

25 3 4 다음에는 9 2 3, 1 5 2 벽돌을 쌓을 수 있고,

25 3 4 -> 9 2 3 다음에는 1 5 2 벽돌

25 3 4 -> 1 5 2 다음은 없다.

그래서 총 두 가지 경로가 존재함을 알 수 있다.

1. 25 3 4 -> 9 2 3 -> 1 5 2
2. 25 3 4 -> 1 5 2

이 두 가지 경로 중에 첫 번째 경로가 높이가 크기 때문에 만약 어떤 벽돌에서 25 3 4를 쌓는 다면 메모제이션해 놓은 1번 경로를 그대로 활용하면 된다.

그래서 한 번 방문하게 되면 중복 방문을 하지 않기 때문에 벽돌의 개수만큼 방문하고, 한 번 방문 했을 때 모든 벽돌을 탐색하기 때문에 O(N^2)으로 문제를 풀 수 있다.

자세한 구현 방법은 소스 코드를 확인하길 바란다.

소스 코드

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

class Info {
    int h;
    String t;
    Info(int h, String t) {
        this.h = h;
        this.t = t;
    }
}

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      int[][] bricks = new int[N + 1][3]; // [i][0] -> 넓이, [1] -> 높이, [2] -> 무게
      for(int i=1; i<=N; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          for(int j=0; j<3; j++) {
              bricks[i][j] = Integer.parseInt(st.nextToken());
          }
      }
      
      Info[] dp = new Info[N + 1]; 
      
      Info ans = new Info(-1, "");
      for(int i=1; i<=N; i++) {
          Info rt = answer(bricks, dp, i);
          if(ans.h < rt.h) {
              ans = rt;
          }
      }
      
      StringBuilder sb = new StringBuilder();
      String[] ansTop = ans.t.split(" ");
      sb.append(ansTop.length).append("\n");
      for(int i=ansTop.length - 1; i>=0; i--) {
          sb.append(ansTop[i]).append("\n");
      }
      
      System.out.println(sb.toString().trim());
      
      
  }
  
  static Info answer(int[][] bricks, Info[] dp, int curIndex) {
      if(dp[curIndex] != null) {
          return dp[curIndex];
      }
      int totalh = bricks[curIndex][1];
      String top = "";
      
      for(int i=1; i<=N; i++) {
          if(bricks[i][0] < bricks[curIndex][0] && bricks[i][2] < bricks[curIndex][2]) {
              //넓이와 무게가 더 작다면 탑을 쌓을 수 있음
              Info info = answer(bricks, dp, i);
              if(totalh < bricks[curIndex][1] + info.h) {
                  totalh = bricks[curIndex][1] + info.h;
                  top = info.t;
              }
          }
      }
      StringBuilder sb = new StringBuilder();
      sb.append(curIndex).append(" ").append(top);
      dp[curIndex] = new Info(totalh, sb.toString());
      
      return dp[curIndex];
  }
}