백준_2655(DP)

우선 벽돌을 밑면의 넓이 순으로 정렬을 시킨다.

그 후 1번 벽돌부터 내 아래에 올 수 있는 벽돌이 무엇인가를 찾으며 높이를 갱신해주면 된다.

현재 선택된 벽돌보다 무거운 벽돌을 찾으면 되는데 무게가 높은 것이 여러개일 경우가 많을 것이다.

따라서 단순히 무게가 높다고 선택하는게 아닌 그 중에서도 높이가 가장 최대가 되는 것을 찾아 dp배열의 높이를 계속해서 갱신해주면 된다.

그렇게 최대 높이를 찾았다면 그 높이를 이용해 기존의 벽돌 배열을 역추적해 어떤 벽돌이 선택되었는지를 찾아주면 된다.

Bricks 배열의 toString은 디버깅 때문에 썼다.

 

package Feb_2022;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Boj_2655 {

    public static class Brick implements Comparable<Brick> {
        int number;
        int wd;
        int h;
        int wt;

        public Brick(int number,int wd, int h, int wt) {
            this.number = number;
            this.wd = wd;
            this.h = h;
            this.wt = wt;
        }

        @Override
        public String toString() {
            return "Brick{" +
                    "wd=" + wd +
                    ", h=" + h +
                    ", wt=" + wt +
                    '}';
        }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        Brick[] bricks = new Brick[N];
        int[] dp = new int[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int wd = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            int wt = Integer.parseInt(st.nextToken());
            bricks[i] = new Brick(i+1,wd, h, wt);
        }
        Arrays.sort(bricks);
        dp[0] = bricks[0].h;

        int result = dp[0];
        for (int i = 1; i < N; i++) {
            int max = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (bricks[j].wt > bricks[i].wt) {
                    if (max < dp[j]) {
                        max = dp[j];
                    }
                }
                dp[i] = max + bricks[i].h;
                result = Math.max(result,dp[i]);
            }
        }

        ArrayList<Integer> arrayList = new ArrayList<>();
        for(int i=N-1;i>=0;i--){
            if(dp[i]==result){
                arrayList.add(bricks[i].number);
                result-=bricks[i].h;
            }
        }

        System.out.println(arrayList.size());
        for(int i=0;i<arrayList.size();i++){
            System.out.println(arrayList.get(i));
        }
    }
}