가장 높은 탑 쌓기 ( + 백준 2655번)(java)

접근

탑을 쌓는 조건이 있는데
밑면의 넓이가 좁은게 넓은 것의 아래 있을 수 없으며
무게가 가벼운 것이 무거운 것 아래 있을 수 없다.

일단 이 문제는 쌓는다는 개념의 문제이기 때문에 저 두개의 조건을 만족하는 가장 긴 수열을 구하는 문제라고 해석된다.

따라서 밑면의 넓이를 기준으로 오름차순으로 벽돌들을 정렬하고
무게라는 조건 하나만을 비교하여 높이가 최대가 될 수 있도록 한다.

만약에
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

위와 같은 입력이 주어진다면

25 3 4
16 2 5
9 2 3
4 4 6
1 5 2
위와 같이 밑면의 넓이를 기준으로 배열을 정렬해야 한다.

또한 벽돌은 밑면의 넓이, 높이, 무게 3가지 속성을 가지고 있기 때문에 이를 내부 클래스로 만들어 객체로 선언될 수 있도록 한다.

풀이 (자바코드)

import java.util.*;
import java.io.*;

public class Main{

    static class Dol{
        int area;
        int h;
        int w;
        public Dol(int area, int h, int w){
            this.area = area;
            this.h = h;
            this.w = w;
        }
    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        Dol[] arr = new Dol[N];
        int[] answer = new int[N];

        StringTokenizer st = null;
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int area = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            arr[i] = new Dol(area,h,w);
        }

        Comparator<Dol> comp = new Comparator<Dol>() {
            @Override
            public int compare(Dol o1, Dol o2) {
                return o2.area - o1.area;
            }
        };

        Arrays.sort(arr,comp);


        answer[0] = arr[0].h;

        for(int i=1;i<N;i++){

            int max = Integer.MIN_VALUE;
            int equal =0;
            boolean tag = false;
            for(int j=0;j<i;j++){
                //몸무게 비교
                if(arr[j].w >= arr[i].w && max<answer[j]){
                    max = answer[j];
                    tag=true;
                    if(arr[j].w == arr[i].w) equal = max;
                }
            }
            if(tag==false) answer[i] = arr[i].h;
            else if(equal==max) answer[i] = equal;
            else answer[i] = max + arr[i].h;


        }

        Arrays.sort(answer);

        bw.write(Integer.toString(answer[N-1]));
        bw.flush();
        bw.close();
        br.close();



    }



}

비슷한 접근법의 문제

비슷하게 접근해야 하는 문제를 발견했다.
백준의 2665번이다.

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

풀이는 아래와 같다.

https://velog.io/@byeolhaha/%EB%B0%B1%EC%A4%80-2655%EB%B2%88-%EA%B0%80%EC%9E%A5%EB%86%92%EC%9D%80%ED%83%91%EC%8C%93%EA%B8%B0-java