가장 높은 탑 쌓기(LIS)

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다.

아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.

(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.

(조건3) 벽돌들의 높이는 같을 수도 있다.

(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.

(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

 

입력

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

10

 

최대 부분 증가수열을 응용한 문제, 무게와 넓이 중 하나를 잡아서 내림차순으로 정렬하면 최대 부분 증가수열과 거의 같은 문제가 된다

 

넓이를 기준으로 오름차순 정렬한 후 i번째 블록이 맨 위에 있을 때 dy[i] = dy[기존까지 블록으로 쌓은 높이 최대] + arr[i] 블록의 높이가 되게 해서 최대값을 찾는다

 

 

import java.util.*;

class block implements Comparable<block>{
    int size;
    int height;
    int weight;
    block(int size, int height, int weight){
        this.size = size;
        this.height = height;
        this.weight = weight;
    }

    @Override
    public int compareTo(block o) {
        return o.size - this.size;
    }
}


class Main{

    static int[] dy;
    public int Solution(ArrayList<block> arr){
       int ans = 0;
       dy = new int[arr.size()];
        //맨 앞 = 제일 무거운 벽돌을 위에 올렸을때 다른 벽돌은 못올라감, 인덱스는 자기의 높이를 가짐
       dy[0] = arr.get(0).height;
        for (int i = 1; i < arr.size(); i++){
            int max = 0;
            for (int j = i -1; j >= 0; j--){
                //i번째 벽돌을 제일 위에 놓았을 때 탑의 높이
                if (arr.get(i).weight < arr.get(j).weight && dy[j] > max) {
                    max = dy[j];
                }
            }
            dy[i] = max + arr.get(i).height;
            ans = Integer.max(dy[i], ans);
        }
        return ans;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<block> arr = new ArrayList<>();
        for (int i = 0; i <n; i++) arr.add(new block(in.nextInt(), in.nextInt(), in.nextInt()));
        Collections.sort(arr);
        System.out.println(T.Solution(arr));
    }
}