leetcode 410 - Split Array Largest Sum

https://leetcode.com/problems/split-array-largest-sum/

풀이

입력된 리스트를 m개로 나눴을 때 sum이 가장 큰 subarray 최소화하는 문제를 한 번에 풀기는 쉽지 않다.

하지만 subarray의 sum이 k가 넘지 않도록 m개로 나눌 수 있냐는 문제는 쉽게 풀 수 있다. sum이 k가 넘지 않는 선까지 최대한 그리디 하게 묶어보면 된다.

 

그러면 문제를 바꿔서 모든 k에 대해 m개로 나눌 수 있는지 확인하는 방법에서 되는데, 여기서 한단계 더 나아가 파라메트릭 서치를 이용할 수 있다. 정답이 k라고 했을 때 k이하의 수에 대해서는 m개로 나눌 수 있고, k보다 큰 수에 대해서는 나눌 수 없는 특성이 있기 때문이다. 이 k를 이분 검색으로 답을 좁혀가면 된다.

 

k의 범위는 최소 0부터 최대 모든 배열의 합인 $10^6 \times 1000$이 된다. 그러면 k로 나눌 수 있는지 질의를 $O(log k)$ 만큼하고, 한번 질의를 할 때 나눌 수 있는지 확인하는데 $O(n)$만큼 걸리기 때문에 총 시간 복잡도는 $O(n log k)$가 된다. 

 

 

코드

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int sum = 0;
        for(int& num : nums)
            sum += num;
        
        int l = 0, r = sum, mid;
        while(l != r-1){
            mid = l + (r - l) / 2;
            if(splitable(nums, m, mid)) r = mid;
            else l = mid;
        }
        return r;
    }
    
    bool splitable(vector<int>& nums, int m, int maxValue){
        int cur = 0;
        for(int& num : nums){
            if(num > maxValue) return false;
            cur += num;
            
            if(cur > maxValue){
                if(--m == 0) return false;
                cur = num;
            }
        }
        return true;
    }
};