데일리썽

문제 제목 : 가장 높은 탑 쌓기

난이도 : 상

문제 유형 : 동적 프로그래밍(DP), LIS

추천 풀이 시간 : 50분 (못하면 2배 100분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

https://www.acmicpc.net/problem/2655

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static class Brick {
        public Integer index;
        public Integer area;
        public Integer height;
        public Integer weight;

        public Brick(Integer index, Integer area, Integer height, Integer weight) {
            this.index = index;
            this.area = area;
            this.height = height;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        ArrayList<Brick> brickList = new ArrayList<Brick>();

        brickList.add(new Brick(0, 0, 0, 0));
        for (int i = 1; i < n + 1; i++) {
            brickList.add(new Brick(i, sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        Collections.sort(brickList, (s1, s2) -> s1.weight - s2.weight);

        int[] dp = new int[n + 1];
        dp[0] = 0;

        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < i; j++) {
                if (brickList.get(i).area > brickList.get(j).area) {
                    dp[i] = Math.max(dp[i], dp[j] + brickList.get(i).height);
                }
            }

        }

        Integer maxHeight = Arrays.stream(dp).max().getAsInt();

        int index = n;
        ArrayList<Integer> resultList = new ArrayList<>();
        while (index != 0) {
            if (maxHeight == dp[index]) {
                resultList.add(brickList.get(index).index);
                maxHeight -= brickList.get(index).height;
            }
            index -= 1;
        }

        System.out.println(resultList.size());
        for (int i = resultList.size() - 1; i >= 0; i--) {
            System.out.println(resultList.get(i));
        }
    }
}