[LeetCode] 1105. Filling Bookcase Shelves

https://leetcode.com/problems/filling-bookcase-shelves/?envType=daily-question&envId=2024-07-31

leetcode - Filling Bookcase Shelves

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

You are given an array books where books[i] = [thicknessi, heighti] indicates the thickness and height of the ith book. You are also given an integer shelfWidth.

We want to place these books in order onto bookcase shelves that have a total width shelfWidth.

We choose some of the books to place on this shelf such that the sum of their thickness is less than or equal to shelfWidth, then build another level of the shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.

Note that at each step of the above process, the order of the books we place is the same order as the given sequence of books.

• For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.

Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

 

당신은 books배열을 받는다, books[i] = 각각의 [두께, 높이]가 주어진다.

정수 shelfWidth도받는다.

책을 너비가 shelfWidth인 책꽃이에 꽃으려고 한다.

책을 골라서 그 층의 책의 두께의 합이 shelfWidth보다 작거나 같아야 한다.

만약 책의 두께들의 합이 넘는다면, 위 층으로 책을 옮길 수 있다.

각 층의 높이는 그 층의 가장 높은 책의 높이로 정해진다.

이 과정을 모든 책에 대해서 반복한다.

주어진 책의 순서대로 책을 추가하여야 한다.

 

위와 같은 방식으로 책꽃이를 만든다 할때, 최소 책꽃이의 총 높이를 구하시오.

 

풀이

처음에는 1층에 추가하고 삐져나오게 한 책을 빼서 위층으로 올리는 로직을 했으나.. 비효율적이기도 하고, 책의 추가 순서만 지키면 되는데, 책상 내부에서 순서를 지킬 필요는 없어서 오답이 나왔었다.

실제 풀이는 다음과 같다:

 

dp[i] = 1번부터 i번째 책을 놓았을 때의 최소 높이합

dp[0]은 책이 없는 경우이므로, 0으로 한다.

 

각 책 i에 대해서, 그 책을 새로운 선반에 놓는 경우와 이전 선반에 놓는 경우를 찾는다.

width로 선반의 너비를 저장하고, height로 선반에 배치된 책들 중 최대 높이를 저장한다.

만약, 현재의 책을 추가했는데 선반의 너비가 넘어버리면, 더이상 책 추가가 불가능하므로 그만둔다,

그렇지 않으면, 현재 책을 포함한 선반의 높이를 게산하고 dp[i]를 업데이트한다.

 

위 설명이 모호해보일 수 있는데, 정리해보자면 두 가지 방법이 있는 것이다.

현재 책을 새로운 선반 층을 만들어서 넣는 방법과, 이전 책을 넣은 층에 합류시키는 방법이 있다.

훨씬 더 이전의 층들은 그 과정의 반복으로 인해 최적화된 층들이 만들어져있다는 의미이다.

그래서 너비의 합이 shelfWidth보다 작거나 같은 동안만 이전 dp의 값에 비교하여 최소값을 구하는 것이다.

코드

C++

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
        int n = books.size();
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;

        for(int i = 1; i <= n; i++) {
            int width = books[i-1][0], height = books[i-1][1];
            dp[i] = dp[i-1] + height;
            for(int j = i-1; j > 0; j--) {
                width += books[j-1][0];
                if(width > shelfWidth) break;
                height = max(height, books[j-1][1]);
                dp[i] = min(dp[i], dp[j-1] + height);
            }
        }

        return dp[n];
        
    }
};