[PS] BOJ2655 가장높은탑쌓기 ( dp ) with JAVA

2655번: 가장높은탑쌓기

 

 

◎ 문제풀이

 

벽돌이 100개 이하로 주어질 때, 벽돌을 쌓아 올릴 수 있는 최대 높이를 구하는 문제이다. 이 문제가 까다로운 이유는 두 개의 조건을 고려해야 하기 때문이다. 

 

1) 밑면의 넓이

2) 무게 

 

이런 경우, 밑면의 넓이로 정렬해준 다음 무게로 DP 풀이를 하면 된다. 먼저, N개의 벽돌을 밑면의 넓이가 작은 순서대로 오름차순 정렬을 한다. 그리고 밑면의 넓이가 작은 것부터 하나씩 DP 테이블을 만들 것이다. DP테이블은 N번째 블록을 가장 밑으로 하는, 즉, 무게도 밑면의 넓이도 가장 큰 경우를 담는다.

 

 

 

 

 

 

벽돌을 밑면의 넓이가 작은 순서대로 오름차순 정렬을 하였다. DP테이블은 인덱스가 매핑되는 벽돌을 가장 밑으로 하는 경우 중, 가장 높이가 높은 경우를 저장해야 한다. 위 그림에서 마지막 경우를 따져보자. 4번 벽돌이 가장 밑으로 깔리는 경우는 DP테이블의 5번 인덱스에 저장된다.

 

4번 벽돌은 이미 밑면의 넓이가 가장 넓은 벽돌이니, 무게만 따지면 된다. 그럼 4번 벽돌의 무게가 5번, 2번, 1번 벽돌보다 무게가 크다고 가정하자. 그럼 DP테이블 1번 인덱스부터 하나씩 비교해보자.

 

 

1번 인덱스 

 

1번 인덱스는 5번 벽돌이고 5번 벽돌보다 무게가 크니 DP 테이블은 아래와 같이 저장된다. 

 

 

 

 

 

2번 인덱스

 

2번 인덱스는 2번 벽돌이고 2번 벽돌보다 무게가 크다. 그러나 이미 DP테이블에는 경우 하나가 저장되어 있다. 그럼 두 가지 경우 중 높이가 가장 큰 경우로 바꾸어 준다. 

 

 

 

 

3번 인덱스 

3번 인덱스의 3번 블록은 5번 인덱스의 4번 블록보다 무게가 나가므로 넘어간다.

 

 

4번 인덱스

4번 인덱스의 5번 블록보다 무게가 크다. 그러나 이미 DP테이블에는 경우가 하나 저장되어 있으므로 두 경우를 비교해준다. 

 

 

결과는 아래 그림과 같다. 

 

 

 

 

 

각 인덱스와 매핑되는 블록을 가장 밑으로 하는 경우들이 완성되었다. 이중에서 높이가 가장 큰 경우를 출력하면 된다. 위 문제는 두 가지 조건을 고려해야 한다는 점과 각 블록을 가장 밑으로 하는 경우의 DP테이블을 구성해야 한다는 점에서 난이도가 있는 문제였다. 

 

 

◎ 코드

 

package org.example.dp;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;


//BOJ2655 가장높은탑쌓기
public class Main {
    public static class Block{
        int num;
        int width;
        int height;
        int weight;

        public Block(int num, int width, int height, int weight) {
            this.num = num;
            this.width = width;
            this.height = height;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        Block[] blocks = new Block[n]; // 블록 리스트 
        List<Block>[] dp = new List[n]; // DP 테이블 
        int[] heights = new int[n]; // 높이 테이블

        StringTokenizer st;
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());

            int width = Integer.parseInt(st.nextToken());
            int height = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            blocks[i] = new Block(i+1,width,height,weight);
            dp[i] = new ArrayList<>();
        }

        Arrays.sort(blocks,(b1,b2)->b1.width - b2.width); // 밑면의 넓이 오름차순 정렬

        // DP 테이블 초기데이터 저장
        dp[0].add(blocks[0]);
        heights[0] = blocks[0].height;
        int maxHeightIndex = 0;

        // DP 테이블 생성 시작
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){ // 이전 블록의 경우와 비교하여 DP 테이블 완성하기 
                if( blocks[i].weight > blocks[j].weight ){ 
                    if( heights[i] <  heights[j] + blocks[i].height ) {
                        dp[i] = dp[j].stream().collect(Collectors.toList());
                        dp[i].add(blocks[i]);
                        heights[i] = heights[j] + blocks[i].height;
                    }
                }
            }
            
            // 조건을 찾지 못한 경우
            if(dp[i].size() == 0){
                dp[i].add(blocks[i]);
                heights[i] = blocks[i].height;
            }

            maxHeightIndex = ( heights[maxHeightIndex] > heights[i] ) ? maxHeightIndex : i;
        }
        
        
        //출력
        sb.append(dp[maxHeightIndex].size()).append("\n"); 
        
        for (Block block : dp[maxHeightIndex]) {
            sb.append(block.num).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}