일련의 책들이 주어져 있다고 가정해 보겠습니다. i번째 책의 두께는 books[i][0]이고, 높이는 books[i][1]입니다. 이 책들을 주어진 순서 그대로, 전체 폭이 shelf_width인 책장에 차례로 꽂으려고 합니다. 몇 권의 책을 한 선반에 함께 놓기로 하면(두께의 합이 shelf_width 이하가 되도록), 그 위에 새로운 선반 단이 하나 더 만들어지며, 책장의 전체 높이는 해당 선반에 놓인 책들 중 가장 큰 높이만큼 증가합니다. 더 이상 놓을 책이 없을 때까지 이 과정을 반복합니다.
여기서 중요한 제약 조건은, 각 단계에서 책을 놓는 순서가 반드시 입력으로 주어진 책 시퀀스의 순서와 동일해야 한다는 점입니다. 목표는 이러한 방식으로 선반을 구성했을 때 전체 책장이 가질 수 있는 최소 높이를 구하는 것입니다.
예를 들어 입력이 [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]이고 shelf_width = 4라고 해보겠습니다.
이때 출력은 6입니다. 세 개의 선반 높이의 합이 1 + 3 + 2 = 6이 되기 때문입니다. 참고로 두 번째 책([2,3])이 반드시 첫 번째 선반에 놓일 필요는 없습니다.
문제 해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. dp[i]를 "i번째 책까지 모두 배치했을 때의 최소 전체 높이"로 정의하고, i번째 책을 마지막으로 포함하는 선반에 앞선 책들을 몇 권까지 함께 묶을지 역방향으로 탐색하면서 최솟값을 갱신하는 방식입니다.
구체적인 알고리즘은 다음과 같습니다.
- 책 배열과 같은 크기의 dp 배열을 생성하고, 모든 값을 무한대(infinite)로 초기화합니다.
- dp[0] := books[0][1] (첫 번째 책 하나만 놓인 경우의 높이)
- i를 1부터 (책 개수 − 1)까지 반복합니다.
- curr_height := 0 (현재 선반에서 가장 큰 책 높이)
- temp := shelf_width (현재 선반에 남은 폭)
- j := i
- j ≥ 0이고 temp − books[j][0] ≥ 0인 동안 다음을 반복합니다.
- curr_height := max(books[j][1], curr_height)
- dp[i] := min(dp[i], curr_height + (j−1 ≥ 0이면 dp[j−1], 아니면 0))
- temp := temp − books[j][0]
- j를 1 감소시킵니다.
- dp 배열의 마지막 요소를 반환합니다.
이해를 돕기 위해 실제 구현 코드를 살펴보겠습니다.
예제 코드
class Solution(object):
def minHeightShelves(self, books, shelf_width):
"""
:type books: List[List[int]]
:type shelf_width: int
:rtype: int
"""
dp = [float('inf') for i in range(len(books))]
dp[0] = books[0][1]
for i in range(1,len(books)):
current_height = 0
temp = shelf_width
j = i
while j>=0 and temp-books[j][0]>=0:
current_height = max(books[j][1],current_height)
dp[i] = min(dp[i],current_height +( dp[j-1] if j-1 >=0 else 0))
temp-=books[j][0]
j-=1
#print(dp)
return dp[-1]입력
[[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]] 4
출력
6
정리
이 알고리즘은 각 위치 i에 대해, i번째 책부터 역방향으로 선반 폭 안에 담을 수 있는 만큼의 책들을 하나의 선반으로 묶는 모든 경우를 확인합니다. 따라서 시간 복잡도는 O(n²)(n은 책의 개수)이며, 공간 복잡도는 O(n)입니다. 동적 계획법을 활용하면 책의 순서를 유지하면서도 전체 책장의 높이를 최소화하는 최적의 배치를 효율적으로 찾을 수 있습니다.