Leetcode - 1011. Capacity To Ship Packages Within D Days

문제

패키지의 무게 배열이 주어지고, 이것들을 나눠서 실을 수 있는 일 수가 주어진다. 최소가 되는 하루 총무게는 얼마인가? (순서는 뒤바뀔수 없고 연속된 패키지를 sub array로 묶어야한다)

가령 아래예시의 경우 5일에 나눠 싣는다고 하면, 모든 경우의 수중에서 15가 하루 최소 무게가 된다.

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

아이디어

• 이게 어떻게 binary search가 되는지 의아할수 있다. (해설을 보며 배운 문제다)
• binary search는 두 종류의 문제가 있다.
  • 배열 인덱스로 binary search 하는 경우 -> O(logn)
  • 어떤 결과 값을 Up & Down 으로 맞추는 경우(주어진 배열을 이용해 계산) -> O(nlogn)
• 이 문제는 최종 답(하루 총 무게)을 Up & Down으로 binary search 하는 문제다. (하루 총 무게의 left/right는 가능한 범위는 미리 계산)
• binary search 템플릿 을 활용, condition() 에서 주어진 배열을 이용해 Up할지 Down할지 계산하면 되는것!
• 아주 훌륭한 문제인것 같다. 많이 배웠다.
• 거의 유사한 유형의 문제로는
  • Leetcode - 410. Split Array Largest Sum [H]

해결

condition()에서 계산하는것은 capacity가 주어질때, 그 값을 기준으로 배열을 나누면 일수를 맞출수 있는지 아닌지를 계산한다.

[1,2,3,4,5,6,7,8,9,10]
              ^

가령 이 경우 capacity가 (10,55의) mid값 32로 주어지면 5번 이하로 나눠서 담기에 충분한 무게치다. 따라서 정답은 32보다 더 작을 가능성이 있다. 따라서 right = 32로 만들고 다시 binary search 하는것이다.

class Solution {
    bool condition(vector<int>& weights, int capa, int tgt_days) {
        // check how many days is needed when using capa value for capacity
        // if needed days are less than the target days, it can be a answer
        // else if needed days is larger than tgt_days, it means that, it is too samll to be a capacity
        int days = 1;
        int sum = 0;
        
        for (int i = 0; i < weights.size(); i++) {
            sum += weights[i];
            if (sum > capa) {
                sum = weights[i];
                days++;
            }
        }
        if (days > tgt_days) // if needed days is larger than tgt_days
            return false;
        return true;
    }
public:
    int shipWithinDays(vector<int>& weights, int days) {
        // <up & down game> for matching capacity value. 
        // <up & down game> will be O(nlogn), not O(logn), because, it is not binary search on the array
        int left = *std::max_element(weights.begin(), weights.end()); // can be a minimum capacity value
        int right = std::accumulate(weights.begin(), weights.end(), 0); // maximun capacity
        int mid = 0;
        
        while (left < right) {
            mid = left + (right - left) / 2;
            if (condition(weights, mid, days)) // mid value can be a capacity but there could be more smaller capacity value
                right = mid;
            else                // mid value is too small to be a capacity, so increasing it. and check condition again.
                left = mid + 1;  
        }
        return left;
    }
};