LeetCode 1011, Capacity To Ship Packages Within D Days 파이썬 풀이 해설
LeetCode 1011, Capacity To Ship Packages Within D Days
접근
- binary-search 로 적절한 배의 weight 용량을 찾는다.
- 처음 lo, hi 는 max(weights), sum(weight) 이다.
- 각각 용량에서 옮기는데 걸리는 날짜를 계산해서, 총 날짜보다 적은 시간으로 옮겼으면 lower bound 를 올리고 아니라면 upper bound를 내린다.
사고
릿코드에 binary search 문제 정말 많다. 기본적으로 이런 유형의 최적값 찾기 binary search 는 lower, upper bound 사이에 조건 충족하는 값이 1개 이상 있다고 전제한다. 조건 days 가 5라면 직관적으로 5를 다 써서 옮기는 수 중에 최적이 있을거 같아보인다. 하지만 4일이나 3일만에 옮기고 그때의 배 용량이 최적일수도 있다. 어쨌거나 우리는 최소 날짜를 구하는게 아니라 최소 용량을 구하는거라 과정을 들여다보면 binary search 가 정말 아름답게 그 값을 찾는다는 것을 알 수 있다.. 문제의 조건을 차근차근 이해함에 따라 binary search 로 뭘 찾을지, bound 는 무엇이고 어떤 경우에 bound 를 어떻게 수정할지도 보인다.
class Solution:
def shipWithinDays(self, weights: list[int], days: int) -> int:
lo, hi = max(weights), sum(weights)
while lo <= hi:
mid = (lo + hi) // 2
spent = 1
acc_weight = 0
for i in range(len(weights)):
if acc_weight + weights[i] > mid:
acc_weight = weights[i]
spent += 1
else:
acc_weight += weights[i]
if spent > days:
lo = mid + 1
else:
hi = mid - 1
return lo
