[코테연습] 1105. Filling Bookcase Shelves

- dp 문제

 

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

 

- 문제분석

1. int[][] books 2중 배열문이 존재. 배열문의 첫번째 요소는 width , 두번쨰 요소는 height 값.

2. 특정 width 값보다 작거나 같을때까지 나열한다.

3. 이때 나열했을때 총 height 값을 구하여라.

 

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n+1];

        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;

        //dp 를 저장할 반복문
        for (int i = 1; i <= n; i++) {
            int totalWidth = 0;
            int maxHeight = 0;
            // i 번째 부터 0까지 역으로 더한다. 
            for (int j = i; j > 0; --j) {
                totalWidth += books[j-1][0];
                //총 더한 값이 shelfWidth 보다 크다면, 멈춘다.
                //즉, shelfWidth 값보다 작을때까지만 더한다. (  4, 3, 2 )
                if (totalWidth > shelfWidth) {
                    break;
                }
                //가장 큰 height 값
                maxHeight = Math.max(maxHeight, books[j-1][1]);
                //현재 dp 값에 갱신.
                dp[i] = Math.min(dp[i], dp[j-1]+maxHeight);
            }
        }

        return dp[n];
    }
}