[Leetcode] 410. Split Array Largest Sum

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

---

음이 아닌 정수로 이루어진 nums 배열과 양수 m 이 주어졌을 때, nums 배열을 비어있지 않은 m개의 연속 하위 배열로 분할 할 수 있다.

분할한 m개의 부분배열 중 가장 큰 합을 최소화 했을 때, 부분배열 합의 최대값을 구해라.

---

이진탐색으로 풀었다.

부분배열 중 가장 큰 합(set, answer)을 이진탐색을 통해서 구하는 방법으로 해보자.

answer가 될 수 있는 값은 제한사항을 보면 nums[i]의 최소값이 0이므로 0에서 nums배열의 합까지 가능하다.

따라서, left = 0, right = sum of nums. 로 한 후 이진탐색을 돌린다.

이진탐색은 medium = (left + right) / 2. 로 구한뒤 medium이 부분배열 합의 최대값보다 같거나 크다면 정답이 될 수 있다. (부분배열 합의 최대값과 완전 같아야 정답이 되지만 이진탐색을 범위를 구하는 것이기 때문에 이진탐색을 돌리면 최대값보다 큰 경우는 걸러질 것이다.)

만약 정답이 될 수 있다면 정답을 갱신하고 정답의 최소값을 구해야 하므로 right를 medium-1로 갱신한다.

정답이 될 수 없다면 left를 medium+1로 갱신한다.

 

이제 medium이 정답이 될 수 있는지 판단하는지 알아보자. 제한사항에서 m은 nums.length보다 작거나 큰 것을 보장하므로 비교적 쉽게 구할 수 있다.

nums 배열을 앞에서부터 탐색하면서 subSum과 분할한 개수 division 변수를 두고 subSum이 sum을 넘는 경우, division+1, subSum = 0 으로 갱신해간다. 조건에서 하위배열은 비어있으면 안되므로 탐색중인 정수가 medium보다 크다면 빈 하위배열이 만들어질 수 있으므로 이 경우 정답이 될 수 없다.

탐색이 끝났을 때, division 수가 m보다 작거나 같으면 정답이 될 수 있고, m보다 크다면 정답이 될 수 없다고 판단한다.

 

시간복잡도는 nums배열의 합을 M, nums 배열 크기를 N이라 한다면 O(NlogM).

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/410.%20Split%20Array%20Largest%20Sum.cpp

---

이제 이진탐색 좀 적응 된걸지도~~?