410. Split Array Largest Sum

[zeikar]

Problem link

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

Problem Summary

배열을 m개의 부분 배열로 나눌 때 각각 부분 배열의 합의 최대가 최소가 되도록 하는 문제.

Solution

처음에 딱 보면 뭔가 어려워 보이는데 잘 생각해보면 이분 탐색으로 꽤 간단히 풀린다. 또는 파라메트릭 서치라고 하는데.. 그냥 이분 탐색이긴 하다.

먼저 이분 탐색으로 타겟을 정한다. 그런 다음 부분 배열의 합이 타겟 값을 넘지 않도록 하면서 배열을 나눠볼 수 있다. 이렇게 나눴을 때 m 개로 나눠지는지 확인하고 나뉜 부분 배열의 개수가 m개보다 적으면 정답을 갱신. m개보다 많다면 타겟 값을 좀 더 올려준다.

처음에 m개보다 적을 땐 정답 갱신을 안했는데 틀렸고, 다시 잘 생각해보면 m개보다 적으면 그냥 중간에 끼워서 나눠주면 되기에 정답일 수 있다.

Source Code

from typing import List


class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def split(target: int) -> (int, int):
            max_sum = 0
            chunk = 0
            cnt = 1

            for num in nums:
                if chunk + num > target:
                    max_sum = max(max_sum, chunk)
                    chunk = num
                    cnt += 1
                else:
                    chunk += num

            max_sum = max(max_sum, chunk)
            return max_sum, cnt

        ans = 1e9
        left = 0
        right = 1e9

        while left <= right:
            mid = (left + right) // 2
            s, groups = split(mid)

            if groups <= m:
                right = mid - 1
                ans = min(ans, s)
            elif groups > m:
                left = mid + 1

        return ans