이 문제에서는 서로 다른 크기의 여러 상자가 주어집니다. 각 상자는 길이(length), 너비(breadth), 높이(height)를 가지며, 상자마다 그 크기가 모두 다를 수 있습니다. 우리의 목표는 이 상자들을 쌓아서 가장 높은 탑을 만드는 것입니다.
흥미로운 점은 상자를 자유롭게 회전할 수 있다는 것입니다. 즉, 어떤 면을 바닥에 둘지 마음대로 정할 수 있습니다. 하지만 반드시 지켜야 할 규칙이 하나 있습니다.
문제의 핵심 규칙
한 상자를 다른 상자 위에 올리려면, 아래 상자 윗면의 넓이가 위 상자 아랫면의 넓이보다 커야 합니다. 이 조건을 만족하는 경우에만 상자를 쌓을 수 있습니다.
이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있는 대표적인 유형입니다. 각 상자를 세 가지 방향으로 회전시켜 총 3n개의 후보를 만들고, 이를 바탕으로 LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)와 유사한 방식으로 최적 해를 구합니다.
입력과 출력 예시
입력:
상자 목록이 주어집니다. 각 상자는 (길이, 너비, 높이)로 표현됩니다.
{ (4, 6, 7), (1, 2, 3), (4, 5, 6), (10, 12, 32) }
출력:
상자 탑의 최대 가능 높이는: 60
알고리즘 접근 방식
maxHeight(boxList, n)
입력 − 서로 다른 상자들의 목록, 상자의 개수 n
출력 − 상자를 쌓아서 얻을 수 있는 최대 높이
알고리즘 단계
- 회전 배열 생성: 각 상자는 3가지 방향으로 놓일 수 있으므로, 크기 3n인 회전(rotation) 배열을 정의합니다. 각 회전마다 가장 긴 변을 '높이'로, 나머지 두 변 중 큰 값을 '밑변', 작은 값을 '너비'로 저장하여 표준화합니다.
- 정렬: 생성된 회전 배열을 밑변(또는 너비) 기준 내림차순으로 정렬합니다.
- 동적 계획법 적용: maxHTemp[i]를 i번째 회전 상자가 탑의 맨 아래에 있을 때의 최대 높이라고 정의합니다. 초기값은 해당 상자의 높이입니다.
- 최적 부분 구조 활용: i번째 상자 위에 j번째 상자(i < j, 정렬 순서상 아래에 위치)를 쌓을 수 있는지 검사합니다. 즉, rot[i]의 밑면과 너비가 rot[j]보다 모두 큰 경우, maxHTemp[i] = maxHTemp[j] + rot[i].height로 갱신합니다.
- 최댓값 반환: 모든 maxHTemp 값 중 최댓값을 찾아 반환합니다.
Begin
크기 3n의 rotation 배열을 정의한다.
index := 0
boxList의 모든 상자 i에 대해 다음을 반복한다.
rotation[index].len := boxList[i].len
rotation[index].hei := boxList[i].hei와 boxList[i].bre 중 최댓값
rotation[index].bre := boxList[i].hei와 boxList[i].bre 중 최솟값
index := index + 1
rotation[index].len := boxList[i].bre
rotation[index].hei := boxList[i].len과 boxList[i].hei 중 최댓값
rotation[index].bre := boxList[i].len과 boxList[i].hei 중 최솟값
index := index + 1
rotation[index].len := boxList[i].hei
rotation[index].hei := boxList[i].len과 boxList[i].bre 중 최댓값
rotation[index].bre := boxList[i].len과 boxList[i].bre 중 최솟값
index := index + 1
n := 3n
rotation 배열을 정렬한다.
maxHeightTemp 배열을 정의한다.
i := 1부터 n-1까지 반복하며,
j := 0부터 i-1까지 반복하면서,
if rotation[i].bre < rotation[j].bre AND
rotation[i].hei < rotation[j].hei AND
maxHeightTemp[i] < maxHeightTemp[j] + rotation[i].len, then
maxHeightTemp[i] := maxHeightTemp[j] + rotation[i].len
반복 종료
maxHeight := -1
i := 0부터 n-1까지,
if maxHeight < maxHeightTemp[i], then
maxHeight := maxHeightTemp[i]
반복 종료
return maxHeight
End
C++ 구현 예제
#include<iostream>
#include<algorithm>
using namespace std;
struct Box {
int length, bredth, height;
};
int min(int x, int y) {
return (x < y)? x : y;
}
int max(int x, int y) {
return (x > y)? x : y;
}
bool compare(Box b1, Box b2) {
return b1.height > b2.height; // 밑면 기준 내림차순 정렬
}
int maxHeight( Box boxList[], int n ) {
Box rotation[3*n]; // 한 상자당 3가지 회전이 가능하므로 총 3n개
int index = 0;
for (int i = 0; i < n; i++) {
// 상자의 초기 위치 저장
rotation[index].length = boxList[i].length;
rotation[index].height = max(boxList[i].height, boxList[i].bredth);
rotation[index].bredth = min(boxList[i].height, boxList[i].bredth);
index++;
// 첫 번째 회전 후의 치수
rotation[index].length = boxList[i].bredth;
rotation[index].height = max(boxList[i].length, boxList[i].height);
rotation[index].bredth = min(boxList[i].length, boxList[i].height);
index++;
// 두 번째 회전 후의 치수
rotation[index].length = boxList[i].height;
rotation[index].height = max(boxList[i].length, boxList[i].bredth);
rotation[index].bredth = min(boxList[i].length, boxList[i].bredth);
index++;
}
n = 3*n; // 각 상자의 3번의 회전을 위해 n을 3n으로 설정
sort(rotation, rotation+n, compare); // rotation 배열을 내림차순 정렬
int maxHTemp[n]; // i번째 상자가 맨 아래에 쌓였을 때의 임시 최대 높이
for (int i = 0; i < n; i++ )
maxHTemp[i] = rotation[i].length;
for (int i = 1; i < n; i++ ) // 최적화된 탑 높이 계산
for (int j = 0; j < i; j++ )
if ( rotation[i].bredth < rotation[j].bredth && rotation[i].height < rotation[j].height
&& maxHTemp[i] < maxHTemp[j] + rotation[i].length) {
maxHTemp[i] = maxHTemp[j] + rotation[i].length;
}
int maxHeight = -1;
for ( int i = 0; i < n; i++ ) // 모든 임시 높이 중 최댓값 탐색
if ( maxHeight < maxHTemp[i] )
maxHeight = maxHTemp[i];
return maxHeight;
}
int main() {
Box arr[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} };
int n = 4;
cout<<"상자 탑의 최대 가능 높이는: " << maxHeight (arr, n) << endl;
}
실행 결과
상자 탑의 최대 가능 높이는: 60
정리 및 시간 복잡도
이 알고리즘은 각 상자를 세 방향으로 회전시켜 문제를 확장한 뒤, 정렬된 순서에서 동적 계획법을 적용합니다. 시간 복잡도는 회전 배열 정렬에 O(3n log 3n), DP 테이블 채우기에 O((3n)²)가 소요되므로 전체적으로 O(n²)입니다. 공간 복잡도는 O(n)입니다.
핵심 포인트는 다음과 같습니다:
- 상자를 회전할 수 있으므로 같은 상자라도 놓이는 방향에 따라 다른 형태로 취급해야 합니다.
- 각 회전에서 가장 긴 변을 세워 높이로 사용하고, 나머지 두 변을 밑면으로 정규화하면 중복 없이 비교할 수 있습니다.
- 밑면 기준으로 정렬한 후, 자신보다 작은 밑면을 가진 상자들 위에 쌓는 경우만 고려하면 됩니다.
- 이는 LIS(최장 증가 부분 수열) 문제와 동일한 구조를 가지므로, DP로 효율적으로 해결할 수 있습니다.