가장 높은 탑 쌓기(Dynamic Programing)

가장 높은 탑 쌓기

 

 

 

코드

package dynamic;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 가장 높은 탑 쌓기(LIS 응용)
 */
public class Dynamic3 {
    // 벽돌 클래스
    static class Brick implements Comparable<Brick> {

        int area;   // 넓이
        int height; // 높이
        int weight; // 무게

        Brick(int area, int height, int weight) {
            this.area = area;
            this.height = height;
            this.weight = weight;
        }

        @Override
        public int compareTo(Brick o) {
            return o.area - this.area; // 넓이 내림차순 정렬
        }
    }

    static int[] dy; // 쌓은 벽돌의 높이를 누적

    static int solution(List<Brick> list) {
        int answer = 0;

        Collections.sort(list); // 넓이에 대해 내림차순 정렬

        dy[0] = list.get(0).height; // 첫 번째 벽돌의 높이로 초기화
        answer = dy[0]; // 첫 번째 벽돌은 무조건 쌓으므로 answer 초기화

        for (int i = 1; i < list.size(); i++) {
            int maxHeight = 0;

            for (int j = i - 1; j >= 0; j--) {
                if (list.get(j).weight > list.get(i).weight && dy[j] > maxHeight) {
                    maxHeight = dy[j];
                }
            }
            // 제일 높게 쌓인 벽돌 위에 i 번째 벽돌 높이 더하기
            dy[i] = maxHeight + list.get(i).height;

            answer = Math.max(answer, dy[i]);
        }


        return answer;
    }


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

        dy = new int[N];
        List<Brick> list = new ArrayList<>();

        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int area = Integer.parseInt(st.nextToken());
            int height  = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            list.add(new Brick(area, height, weight));
        }

        System.out.println(solution(list));
    }
}

 

풀이

1. 벽돌 클래스를 만들어 정렬 기준을 넓이 내림차순으로 한다.

2. dy[ j ] 번째 벽돌이 dy [ i ] 번 째 벽돌 보다 무게가 적고,  dy[ j ] 번째 중 높이가 가장 높게 쌓인(maxHeight) 벽돌 위에 i 번째 벽돌의 높이를 더해서 초기화한다.

 

이번 문제는 최대 부분 증가수열 문제와 유사한 구조로 풀이법은 동일하다.