[Inflearn] 자바 알고리즘 문제풀이 #10-04 4.가장 높은 탑 쌓기(LIS 응용)

문제

설명

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

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

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

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

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

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

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

 

입력

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

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

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

 

출력

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

 

예시 입력 1 

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

예시 출력 1

10

 

 

 

내 풀이

import java.util.Scanner;

class Block {
    int area, height, weight;
    public Block(int area, int height, int weight){
        this.area = area;
        this.height = height;
        this.weight = weight;
    }
}
public class Main10_4 {
    static int[] dy;
    public int Solution(Block[] arr){
        int answer=0;
        dy = new int[arr.length];
        dy[0] = arr[0].height;
        for (int i = 1; i < dy.length; i++) {
            int max = 0;
            for (int j = i-1; j >= 0; j--) {
                if(arr[j].area > arr[i].area && arr[j].weight > arr[i].weight && dy[j]>max) max = dy[j];
            }
            dy[i] = arr[i].height + max;
            answer = Math.max(answer, dy[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main10_4 T = new Main10_4();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Block[] arr = new Block[n];
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            arr[i] = new Block(a, b, c);
        }
        System.out.println(T.Solution(arr));
    }
}

 

 

 

선생님 풀이

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

class Brick implements Comparable<Brick> {
    public int s, h, w;
    public Brick(int s, int h, int w){
        this.s = s;
        this.h = h;
        this.w = w;
    }
    @Override
    public int compareTo(Brick o){
        return o.s - this.s;
    }
}
public class Main10_4 {
    static int[] dy;
    public int Solution(ArrayList<Brick> arr){
        int answer=0;
        Collections.sort(arr);
        dy[0] = arr.get(0).h;
        answer=dy[0];
        for (int i = 1; i < dy.length; i++) {
            int max_h=0;
            for (int j = i-1; j >= 0; j--) {
                if(arr.get(j).w > arr.get(i).w && dy[j]>max_h) max_h = dy[j];
            }
            dy[i] = arr.get(i).h + max_h;
            answer = Math.max(answer, dy[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main10_4 T = new Main10_4();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        dy = new int[n];
        ArrayList<Brick> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            arr.add(new Brick(a, b, c));
        }
        System.out.println(T.Solution(arr));
    }
}

DP에서는 dy배열의 의미 설정이 가장 중요한 것 같다.

쉬워보이지만 막상 풀어보면 생각보다 안풀리는 너낌... 이래서 어렵다고 하는건가?!

이 문제에서는 dy[i] = i번째 벽돌을 탑의 제일 위에 놓았을 때 탑의 최대 높이로 두고 풀면 된다.

 

 

10-03문제와 다르게 answer값을 dy[0]으로 초기화한다.

그 이유는 만약에 arr에 (25, 10, 3) (16, 2, 6) (10, 5, 9) Brick 객체가 있다고 가정할 때

첫 번째 객체 위에 아무것도 올릴 수 없기 때문에 answer값을 dy[0]으로 초기화 해주지 않으면 0이 출력돼 오답이 된다.

10-03문제랑 비교해서 이해하면 좋을 것 같다.

 

 

 

 

결과