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

접근

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

이 문제는 5가지 조건에 의해서 탑을 쌓을 수 있다.
벽돌이 2개가 쌓아져 있다고 가정할 때
밑에 벽돌이 위에 벽돌보다 무게가 더 나가고 밑면의 넓이가 더 큰것이어야만 한다.
이 두 가지 조건을 모두 만족해야만 쌓을 수 있다.

일반 최장증가부분수열(LIS, Longest Increasing Subsequence) 알고리즘을 생각해본다면
최장증가부분수열은 쌓되, 하나의 비교만을 한다. 벽돌이라고 가정했을 때 무게만 비교한다고 볼 수 있다.

근데 이 문제는 최장증가부분수열에 2가지의 조건이 추가되었고 심지어 벽돌에 번호를 부여해서
높이가 가장 높은 탑에 어떤 벽돌이 어떤 순서로 쌓아져 있는지 구하라고 한다.

(이 문제를 보고 이게 최장증가부분수열이라는 것을 깨달을 정도로 연습이 필요할거 같다.)

방법

일단 나는 2개의 내부 클래스를 만들었다.

• 하나는 벽돌에 속성을 넣어주는 클래스이다.
  벽돌에는 번호, 높이, 넓이, 무게가 넣어져 있어야 하므로 내부 클래스로 하나의 객체로 인식되게 설정한다.

 static class Dol{
        int area;//밑변의 넓이
        int h; // 높이
        int w; // 무게
        int index; // 벽돌의 번호
        public Dol(int area, int h, int w, int index){
            this.area = area;
            this.h = h;
            this.w = w;
            this.index= index;
        }
    }

두개의 조건을 비교해야 하므로 일단 먼저 정렬을 통해서 높이가 높은 순으로 배열을 정렬하도록 하고 실제로 비교하는 값은 높이가 정렬된 배열의 무게가 될 것이다.

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

무게로 비교하되 높이가 높은 쪽의 탑을 선택하도록 비교하는 조건문이 필요하다.

• 나머지 하나는 탑을 누적하기 위해 내부 클래스이다.
  이 내부 클래스에는 지금까지 쌓여진 탑의 높이의 합, 쌓여진 벽돌의 수, 쌓여진 벽돌의 번호가 속성으로 들어간다.

static class Anw{
        int height; // 지금까지 쌓여진 탑의 높이의 합
        int num; // 쌓여진 벽돌의 수
        String index; // 쌓여진 벽돌의 번호들 
        public Anw(int height, int num, String index){
            this.height = height;
            this.num = num;
            this.index = index;
        }
    }

또한 마지막에 높이가 가장 높은 탑의 값을 출력하기 위해서 배열의 정렬이 필요하다.

  Comparator<Anw> comp1 = new Comparator<Anw>() {
            @Override
            public int compare(Anw o1, Anw o2) {
                return o2.height - o1.height;
            }
        };

풀이(자바코드)

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

public class Main{

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

    static class Anw{
        int height;
        int num;
        String index;
        public Anw(int height, int num, String index){
            this.height = height;
            this.num = num;
            this.index = index;
        }
    }



    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];
        Anw[] answer = new Anw[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,i+1);
        }

        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]=new Anw(arr[0].h,1,arr[0].index+" ");


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

            int max = Integer.MIN_VALUE;
            int equal =0;
            boolean tag = false;
            int index=0;

            for(int j=0;j<i;j++){
                //몸무게 비교
                if(arr[j].w >= arr[i].w && max<answer[j].height){
                    max = answer[j].height;
                    tag=true;
                    if(arr[j].w == arr[i].w) equal = max;
                    index=j;
                }
            }
            if(tag==false) {
                answer[i] = new Anw(arr[i].h,1,arr[i].index+" ");
            }
            else if(equal==max) {
                answer[i] = new Anw(max,answer[index].num,arr[index].index+" ");
            }
            else{
                answer[i] = new Anw(max + arr[i].h,answer[index].num+1,
                        answer[index].index+arr[i].index+" ");
            }


        }

        Comparator<Anw> comp1 = new Comparator<Anw>() {
            @Override
            public int compare(Anw o1, Anw o2) {
                return o2.height - o1.height;
            }
        };
        Arrays.sort(answer,comp1);
        int num_buck = answer[0].num;
        bw.write(Integer.toString(num_buck)+"\n");
        String[] top = answer[0].index.split(" ");
        for(int i= top.length-1;i>=0;i--)
            bw.write(top[i]+"\n");
        bw.flush();
        bw.close();
        br.close();



    }



}