[leetcode] 이진탐색 1011. Capacity To Ship Packages Within D Days

컨베이어 벨트에는 수일 내에 한 항구에서 다른 항구로 배송되어야 하는 패키지가 있습니다.

컨베이어 벨트에 있는 i번째 패키지 무게는 weights[i]입니다.

매일 우리는 컨베이어 벨트에 패키지를 싣습니다(제공되는 weights의 순서대로)

선박의 최대적재용량을 초과하여 적재할 수 없습니다.

컨베이어 벨트의 모든 패키지가 주어진 days 내에 배송될 수 있도록 선박의 최소 적재용량을 반환합니다.

 

example

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

 

이진탐색

 

weights 리스트에서 하나씩  대입하여 최대적재용량을 찾으면 된다.

시간초과가 생기기때문에 이진탐색으로 진행한다.

최대한 day마다 package를 넣어야 된다.

최대적재용량을 mid로 정하고 주어진 days보다 크면 최대적재용량을 올리고, 아니면 내린다.

 

weights = [1,2,3,4,5]
D = 3

lo,hi = max(weights), sum(weights)
while lo < hi:
    day = 1
    wt = 0
    mid = (lo + hi)//2
    for w in weights:
        if wt + w > mid:
            day +=1
            wt =0
        wt += w
    if day <= D:
        hi = mid
    else:
        lo = mid+1
print(lo)