[Java] 가장 높은 탑 쌓기 (LIS 응용)

---

가장 높은 탑 쌓기 (LIS 응용)

밑면이 정사각형인 직육면체 벽돌들을 사용하여 가장 높게 쌓을 수 있는 높이를 구해야 한다.

벽돌은 넓이, 높이, 무게 값을 가진다.

하나의 벽돌 위에는 더 작은 넓이, 더 작은 무게를 가진 벽돌만 쌓을 수 있다.

첫 째줄에 벽돌의 개수 N 이 주어지고,
이후 나오는 N 개의 줄에 벽돌의 넓이(s), 높이(h), 무게(w) 가 주어진다.

입력 예시

4
16 3 2
25 9 13
4 7 7
1 1 1

Solution

우선, 입력받은 벽돌들을 넓이 기준으로 내림차순으로 정렬하고, 순차적으로 탐색하며 무게만 비교하며 최적의 경우를 찾을 수 있도록 해보자.

	0	1	2	3
s	25	16	4	1
h	9	3	7	1
w	13	2	7	1

DP 테이블 dy[]

dy[i] 가 의미하는 것은 i 번째 벽돌을 탑의 맨 위에 두었을 경우 가장 높은 탑의 높이를 의미한다.

dy 배열 중에서 가장 높은 값을 구한다면 그 값이 주어진 벽돌로 쌓을 수 있는 최대 높이일 것이다.

문제 풀이 과정은 아래와 같이 이루어진다.

1. 지금 벽돌이 이전 벽돌 위에 올라갈 수 있는지 체크
2. 올라갈 수 있는 벽돌 중에서 높이가 가장 높은 벽돌과의 합을 저장
3. 끝까지 반복 후 가장 높은 값을 출력

dy[0] 은 0번 벽돌이 가장 위에 있을 경우의 최대 높이를 의미하므로
dy[0] 는 0번 벽돌의 높이와 같다.

dy[1] 의 경우 무게가 0번 벽돌보다 작기 때문에 위에 쌓을 수 있기 때문에
dy[1] 는 dy[0] + 1번 벽돌의 높이 이다.

dy[2] 의 경우 dy[0]의 경우 0번 벽돌 위에 쌓을 수 있고, dy[1] 의 경우 1번 벽돌 위에도 쌓을 수 있다. 이 중에서 dy[1] 보다 dy[0] 의 값이 더 크기 때문에 dy[2] 는 dy[0] + 2번 벽돌의 높이가 된다.

이와 같은 방법으로 n-1번 벽돌까지 dy 값을 구하고 그중 최대 값을 구하면 정답을 구할 수 있다.

dy[]

	0	1	2	3
dy	9	12	16	17

dy[3] 이 17로 가장 높은 값을 가진다.
3번벽돌이 가장 위에 있을 경우 0 -> 2 -> 3 순서로 쌓아 높이가 17로 가장 높다는 것을 구할 수 있다.

소스코드

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

        ArrayList<Brick> arr = new ArrayList<>();
        int dy[] = new int[n];


        for (int i = 0; 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());

            arr.add(new Brick(s, h, w));
        }
        Collections.sort(arr);

        dy[0] = arr.get(0).h;
        for (int i = 1; i < n; i++) {
            int maxH = 0;
            for (int j = 0; j < i ; j++) {
                if (arr.get(i).w < arr.get(j).w) {
                    if (dy[j] > maxH) {
                        maxH = dy[j];
                    }
                }
            }
            dy[i] = maxH + arr.get(i).h;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (ans < dy[i]) {
                ans = dy[i];
            }
        }
        System.out.println(ans);
    }
}

class Brick implements Comparable<Brick> {

    int s;
    int h;
    int w;

    public Brick(int s, int h, int w) {
        this.s = s;
        this.h = h;
        this.w = w;
    }

    @Override
    public int compareTo(Brick o) {
        return o.s - this.s;
    }
}