paremetic search1 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를 이분 검색으로 답을 좁혀가면 된다... 2020. 10. 6. 이전 1 다음
