[백준] 2655번 가장 높은 탑 쌓기 (자바 풀이)

문제

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

2655번: 가장높은탑쌓기

풀이

이 문제는 아래와 같은 제약 조건들이 존재한다.

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

결국 중요한 것은 밑면의 넓이가 더 넓고 무게가 더 무거운 벽돌이 아래로 가야한다는 것이다.

벽돌 class를 정의하고, 밑면의 넓이, 무게, 높이를 멤버로 갖게 한다. 밑면의 넓이 혹은 무게를 기준으로 오름차순으로 정렬하여 사용하면 된다. 나는 밑면의 넓이를 기준으로 오름차순으로 원소들을 정렬했다.

 

이후 DP를 이용하여 최대 높이를 계산하면 된다. 

점화식은 다음과 같다.

 

dp[i] = Math.max(dp[i], dp[j]+현재 벽돌의 높이) 

여기서 j는 i번째 벽돌 위에 쌓인 벽돌들이다. 즉, dp[j]는 j번째 벽돌이 아래로 깔렸을 때의 최대 높이다.

 

예제를 예시로 들어보자.

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

위와 같은 입력이 들어온다면, 밑면의 넓이를 기준으로 정렬하면 다음과 같이 된다.

벽돌 넘버(num)	밑면의 넓이(s)	벽돌의 높이(h)	벽돌의 무게(w)
5	1	5	2
2	4	4	6
3	9	2	3
4	16	2	5
1	25	3	4

이것을 기준으로 dp 배열을 구하면 다음과 같다. 

dp[i]	0	1	2	3	4	5
	0	0	0	0	0	0
	0	5	0	0	0	0
	0	5	9	0	0	0
	0	5	9	7	0	0
	0	5	9	7	9	0
	0	5	9	7	9	10

코드

import java.util.*;
import java.io.*;
 
public class Baekjoon_2655 {
    static int N;
    static Brick list[];
    static int dp[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        list = new Brick[N+1];
        dp = new int[N+1];
        Arrays.fill(dp, 0);
        list[0] = new Brick(0,0,0,0);
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int s = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list[i] = new Brick(i,s,h,w);
        }
        
        
        /* 람다식을 이용한 밑면 넓이 기준 오름차순 정렬 */
        Arrays.sort(list, (o1,o2) -> o1.s - o2.s );
        
        int max = 0;
        for(int i=1; i<=N; i++) {
            for(int j=0; j<i; j++) {
                if(list[i].w > list[j].w ) {
                    dp[i] = Math.max(dp[i], dp[j]+list[i].h);
                }
            }
            max = Math.max(max, dp[i]);
        }
        
        Stack<Integer> ans = new Stack<>();
        while(N > 0) {
            if(max == dp[N]){ 
                ans.add(list[N].num);
                max -= list[N].h;
            }
            N--;
        }
        
        System.out.println(ans.size());
        while(!ans.isEmpty()) {
            System.out.println(ans.pop());
        }
        
            
    }
    
    static class Brick{
        int num;    // 벽돌 번호
        int s;    // 벽돌 밑면
        int h;    // 벽돌 높이
        int w;    // 벽돌 무게
        Brick(int num, int s, int h, int w){
            this.num = num;
            this.s = s;
            this.h = h;
            this.w = w;
        }
    }
 
}
 

결과