1105. Filling Bookcase Shelves

[zeikar]

Problem link

https://leetcode.com/problems/filling-bookcase-shelves/

Problem Summary

책을 책장에 꽂아 넣을 때 높이가 최소가 되도록 꽂는 문제.

Solution

DP 문제이다.
책을 꽂는 방식이 2가지가 있고 현재 shelf에 꽂을지 혹은 다음 shelf로 꽂을지 선택할 수 있다. 책의 너비가 전체 shelf 보다 크지 않으면 한 shelf로 다 꽂을 수 있다.

dp[i] = i번째 부터의 책을 새로운 shelf로 꽂을 때의 최소 높이.

로 두고, 한 줄에 꽂을 수 있을 때까지 꽂으면서 top-down dp로 구현하면 된다.

Source Code

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)

        @cache
        def putBook(bookIdx):
            if bookIdx == n:
                return 0

            width = 0
            maxHeight = 0
            ret = 987654321
            for i in range(bookIdx, n):
                [t, h] = books[i]
                width += t

                if width > shelfWidth:
                    break

                maxHeight = max(maxHeight, h)
                ret = min(ret, putBook(i + 1) + maxHeight)

            return ret

        return putBook(0)