섹션 10 Dynamic Programming - 4. 가장 높은 탑 쌓기(LIS 응용)

설명

밑면이 정사각형인 벽돌들을 아래에서 위로 쌓아 올려 가장 높게 탑을 만드는 문제입니다.
단, 벽돌을 쌓을 때 아래 조건들을 반드시 지켜야 합니다.

쌓을 수 있는 조건

1. 벽돌은 회전 불가 (가로세로 바꿔서 쓸 수 없음)
2. 밑면 넓이가 큰 벽돌만 작은 벽돌 위에 올 수 있음
3. 무게가 더 가벼운 벽돌 위에 무거운 벽돌을 올릴 수 없음
4. 밑면 넓이와 무게가 같은 벽돌은 없다 (→ 중복을 신경 쓸 필요 없음)

---

입력

• 첫 줄: 벽돌의 수 N (1 ≤ N ≤ 100)
• 다음 줄부터: 각 벽돌의 (밑면 넓이, 높이, 무게) 정보가 주어짐
• 모든 값은 10,000 이하의 자연수

---

출력

• 만들 수 있는 가장 높은 탑의 총 높이

---

🔍 예시

예시 입력

 

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

예시 출력

 

10

---

해결 방법

1. 넓이 기준 내림차순 정렬
   • 밑면 넓이 기준으로 정렬하면 이후에는 넓이 조건은 자동으로 만족하게 됩니다.
   • 따라서 DP에서는 무게만 비교하면 됩니다.
2. DP 배열 의미 (dy[i])
   • dy[i]는 i번째 벽돌을 꼭대기에 두었을 때 만들 수 있는 최대 높이를 저장합니다.
   • 이전 문제 LIS에서 dp[i] = max(dp[j]) + 1처럼, 여기선 dy[i] = max(dy[j]) + arr[i].h로 표현됩니다.
3. 탑을 쌓는 조건
   • arr[j].w > arr[i].w이면 무게가 더 무거운 벽돌이 더 아래에 놓인 것이므로 유효합니다.
   • 넓이 조건은 정렬로 보장되므로 무게 조건만 검사하면 됩니다.

 

---

코드 구현

import java.util.*;

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 ob) {
		return ob.s - this.s; // 내림차순 정렬 (넓이가 큰 벽돌 먼저)
	}
}

public class Main {
	static int[] dy;
	static int n;
	
	public int solution(ArrayList<Brick> arr) {
		int answer;

		Collections.sort(arr); // 넓이 기준 내림차순 정렬
		dy[0] = arr.get(0).h;
		answer = dy[0];
		
		for(int i=1; i<n; i++) {
			int max = 0;
			for(int j=i-1; j>=0; j--) {
				if(arr.get(j).w > arr.get(i).w && dy[j] > max) {
					max = dy[j];
				}
			}
			dy[i] = max + arr.get(i).h;
			answer = Math.max(answer, dy[i]);
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		dy = new int[n];
		ArrayList<Brick> arr = new ArrayList<>();
		for(int i=0; i<n; i++) {
			int s = sc.nextInt();
			int h = sc.nextInt();
			int w = sc.nextInt();
			arr.add(new Brick(s, h, w));
		}
		System.out.print(T.solution(arr));
		sc.close();
	}
}

 

---

코드 설명

• Brick 클래스: 벽돌의 넓이(s), 높이(h), 무게(w)를 필드로 가짐
• compareTo: 넓이 기준으로 내림차순 정렬 → 밑면 넓이가 큰 순서대로 정렬됨
• dy[i]: i번째 벽돌을 가장 위에 올렸을 때 만들 수 있는 최대 탑의 높이
• dy[i] = max(dy[j]) + arr[i].h → i보다 넓이/무게가 모두 큰 j 벽돌들 중에서 가장 높은 곳에 이어 쌓기

---

시간 복잡도 분석

• O(N²) : 이중 for문으로 i와 j를 비교하면서 조건에 맞는 벽돌을 쌓는 방식

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런