가장 높은 탑 쌓기

가장 높은 탑 쌓기

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다.

아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.

(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.

(조건3) 벽돌들의 높이는 같을 수도 있다.

(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.

(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

입력 설명

입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다.

둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다.

각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.

출력 설명

첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.

입력

5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

출력

10

구현 코드

public class 가장높은탑쌓기 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        Brick[] arr = new Brick[n];
        Integer[] dy = new Integer[n];
        Arrays.fill(dy,0);

        for(int i=0;i<n;i++){
            arr[i] = new Brick(in.nextInt(),in.nextInt(),in.nextInt());
        }

        Arrays.sort(arr);

        for(int i=0;i<n;i++){
            int maxLength = 0;
            for(int j=i;j>=0;j--){
                if(arr[i].s<arr[j].s && arr[i].w<arr[j].w){
                    //현재 보다 넓이가 넓고 무게가 무거운 경우
                    if(maxLength<=dy[j]){
                        maxLength = dy[j];
                    }
                }
            }
            dy[i] = maxLength + arr[i].h;
        }

        Arrays.sort(dy, Collections.reverseOrder());
        System.out.println(dy[0]);
    }

    static class Brick implements Comparable<Brick>{
        public Brick(int s, int h, int w) {
            this.s = s;
            this.h = h;
            this.w = w;
        }

        int s; //밑면 넓이
        int h; //높이
        int w; //무게

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

전반적인 구현 흐름은 이전 LIS 문제와 같음. 단 비교조건만 다름.

• 알고리즘

  순서를 지켜야한다는 명시가 없으므로 넓이가 긴 것부터 오름차순 정렬하고 시작 ( 이 부분을 생각못해서 그냥 짰다가 오답이 여러번 나옴)
  이중 for
  밑에 쌓이는 벽돌이 위에 쌓이는 벽돌보다 무게와 넓이 값이 커야 하므로 조건 걸어줌 & dy 업데이트(업데이트 시 높이 값으로 업데이트)
  dy 내림차순 정렬 후 최대값 출력