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

여기도 마찬가지로 dy[i]를 사용

dy[i]는 i 번째 벽돌을 마지막으로 하는 최대 벽돌의 높이를 저장할 배열임

앞의 문제와 비슷하나 이전 벽돌 보다 좁아야하고 무게도 가벼워야한다.

따라서 현 지점이 더 커야 수열을 만드는 앞의 문제와는 달리

지금 문제는 현 지점의 무게가 더 작아야 쌓을 수 있다.

무게만 비교해주기 위해 벽돌의 넓이를 기준으로 내림차순 정렬

무게만 가볍다면 위의 벽돌로 쌓을 수 있다.

 

import java.util.*;
class Brick implements Comparable<Brick>{
    public int s, h, w;
    
    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;
    }
}
class Main{
    static int[] dy;
    
    public int solution(ArrayList<Brick> arr){
        int answer=0;
        Collections.sort(arr);
        dy[0]=arr.get(0).h;
        //앞의 문제와는 다르게 위에 벽돌 쌓을 수 없으면 이게 답이 되야함
        answer=dy[0];
        for(int i = 1; i < arr.size(); i++) {
            int max_h=0;
            for(int j = i - 1; j >= 0; j--){
                //이전 벽돌보다 가벼운(올릴 수 있는) 것 중 제일 큰 높이를 max 값으로 둔다.
                //이전 항이 무게가 더 무거워야 올릴 수 있음
                if(arr.get(j).w > arr.get(i).w && dy[j]>max_h){
                    max_h=dy[j];
                }
            }
            //i번째 벽돌 올리기
            dy[i]=max_h+arr.get(i).h;
            answer=Math.max(answer, dy[i]);
        }
        return answer;
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        ArrayList<Brick> arr=new ArrayList<>();
        dy=new int[n];
        for(int i=0; i<n; i++){
            int a=kb.nextInt();
            int b=kb.nextInt();
            int c=kb.nextInt();
            arr.add(new Brick(a, b, c));
        }
        System.out.print(T.solution(arr));
    }
}