[알고리즘] 6번째 알고리즘 문제 풀기 개인

[ujkkk]

📝 Description

❗️Todo

• [x] https://leetcode.com/problems/filling-bookcase-shelves/description/
• [x] https://leetcode.com/problems/search-in-rotated-sorted-array/description/

[ujkkk]

1105. Filling Bookcase Shelves

통과는 되었지만 걸린 시간이 상위 90%임... 더 좋은 방법 없을까

import java.util.*;
class Solution {

    public static int min;
    public static int [][] dp;

    public static int minHeightShelves(int[][] books, int shelfWidth) {
        // dp[n번째][사용한 width] -> n번째 책을 꽂았을 때 최소 길이
        dp = new int[books.length+1][shelfWidth+1];
        min = Integer.MAX_VALUE-1000;

        for(int i=0; i<books.length; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        // 첫 번째 책 배치
        dp[0][books[0][0]] = books[0][1];
        getMinShelfHeight(books, shelfWidth,1, books[0][0], 0);

        return min;
    }

    public static void getMinShelfHeight(int[][] books, int shelfWidth, int n, int usedWidth, int usedHeight){
        if(n == books.length){
            min=Math.min(min ,dp[n-1][usedWidth]);
            return;
        }

        // 1. 이전 책과 같은 선반에 배치
        if(usedWidth + books[n][0] <= shelfWidth){
            int newUsedWidth = usedWidth + books[n][0];
            int newHeight = Math.max(dp[n-1][usedWidth], usedHeight + books[n][1]);

            // 갱신되면 탐색
            if(newHeight < dp[n][newUsedWidth]){
                dp[n][newUsedWidth] = newHeight;
                getMinShelfHeight(books, shelfWidth, n+1, newUsedWidth, usedHeight);
            }
        }
        // 2. 새 선반에 배치
        if(dp[n-1][usedWidth] + books[n][1] < dp[n][books[n][0]]){
            dp[n][books[n][0]] = dp[n-1][usedWidth] + books[n][1];
            getMinShelfHeight(books, shelfWidth, n+1, books[n][0], dp[n-1][usedWidth]);
        }
    }
}

[ujkkk]

두 번째 문제는 시도했지만 결국 못 풀었다...

놓친부분은 고정적인 부분을 기준으로 잡고 if, else를 나눠야 했는데 유동적인것을 잡고 계속 이리 저리 분류를 하려고 해서 못 풀었다.

즉 나는 start ~ end 사이에 피봇이 있냐 없냐 나눴는데 그러다보니 확신정보가 없었다.