가장 높은 탑 쌓기(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.*;
class Brick implements Comparable<Brick> {
public int s, h, w;
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;
}
}
class Main {
static int[] dy;
public int solution(ArrayList<Brick> arr) {
int answer = 0;
// 정렬하고 시작. 정렬 기준은 밑몉이 넓은 순서대로.
Collections.sort(arr);
// 초기화 -> 0번째는 높이로 바로 값을 세팅.
dy[0] = arr.get(0).h;
// 정답에 넣고 시작.
answer = dy[0];
// 반복하면서 벽돌 수 만큼 반복.
for (int i = 1; i < arr.size(); 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] = max_h + arr.get(i).h;
// 최대값을 비교하여 정답 교체
answer = Math.max(answer, dy[i]);
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
ArrayList<Brick> arr = new ArrayList<>();
dy = new int[n];
// 각 줄에 입력된 값을 객체로 치환하여 배열에 저장한다.
for (int i = 0; i < n; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
int c = kb.nextInt();
arr.add(new Brick(a, b, c));
}
System.out.print(T.solution(arr));
}
}
