Leetcode - 410. Split Array Largest Sum [H]

문제

주어진 배열을 m개로 나눌때(연속된 sub array로), m개의 sub array합중에 가장큰값이, 모든 경우의수에서 가장 최소가 되게하는 알고리즘을 작성해라.
(Write an algorithm to minimize the largest sum among these m subarrays.)

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

아이디어

• Up & Down 게임 binary search 유형의 문제. 풀이는 아래 문제와 거의 완전동일하다. 해설은 아래 글에 작성했음.
  • Leetcode - 1011. Capacity To Ship Packages Within D Days

해결

class Solution {
    bool check_mid_capable(vector<int> nums, int candidate, int tgt_split) {
        // check how many split with candidate value
        int split = 1;
        int sum = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (sum > candidate) {
                sum = nums[i];
                split++;
            }
        }
        if (split > tgt_split) // if candidate value sperate more than m, then false 
            return false;
        return true;
    }
public:
    int splitArray(vector<int>& nums, int m) {
        int left = *std::max_element(nums.begin(), nums.end());
        int right = std::accumulate(nums.begin(), nums.end(), 0);
        int mid = 0;
        
        while (left < right) {
            mid = left + (right - left) / 2;
            if (check_mid_capable(nums, mid, m))    // if mid can seperate m times. it means there could be more small value exist.
                right = mid;
            else                                    // means mid value is too small,
                left = mid + 1;
        }
        return left;
    }
};