[JAVA] 알고리즘 : 동적 계획법- 가장 높은 탑 쌓기

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

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; // 넓이 내림차순
    }
}
public class Main{
    static int[] dp;
    public int solution(ArrayList<Brick> arr){
        int answer=0;
        Collections.sort(arr); // 넓이 내림차순으로 정렬
        dp[0] = arr.get(0).h; // 첫번째 벽돌 높이로 초기화
        answer = dp[0]; 
        for(int i=1; i<arr.size(); i++){
            int max_h=0;
            for(int j=i-1; j>=0; j--){
                if(arr.get(j).w>arr.get(i).w && dp[j]>max_h){ // i번째 벽돌보다 무게가 더 큰 벽돌 중 높이 최댓값 구함
                    max_h = dp[j];
                }
            }
            dp[i] = max_h + arr.get(i).h;
            answer = Math.max(answer, dp[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<>();
        dp=new int[n]; // 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.println(T.solution(arr));
    }
}