[LeetCode] 410 | Split Array Largest Sum | Python

---

문제 링크: https://leetcode.com/problems/split-array-largest-sum/

---

문제

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

---

조건

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 106
• 1 <= m <= min(50, nums.length)

---

내 풀이

문제를 보면 binary search를 이용해야한다는 느낌이 오지만 어떻게 해야할 지 감이 오지 않을 수 있다.

그 이유는 문제에 생각이 매몰되어서 subarray sum만 생각하게되기 때문이다.

그 생각에서 벗어나 subarray 개수를 함께 이용하면 문제는 쉽게 해결된다.

 

subarray sum을 binary search로 찾으면서 그때마다 subarray가 몇 개 생성되는지 확인한다.

---

코드

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        left, right = max(nums), sum(nums)
        self.nums = nums
        
        while left < right:
            mid = (left + right) // 2
            count = self.NumberofSubarray(mid)
            
            if count <= m:
                right = mid
            else:
                left = mid + 1
        
        return left
        
    def NumberofSubarray(self, subarraySum):
        count, curSum = 0, 0
        for num in self.nums:
            if curSum - num < 0:
                curSum = subarraySum - num
                count += 1
            else:
                curSum -= num
        
        return count