[내일배움캠프] 4주차 숙제 Q1: 농심 라면 공장

문제

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

 

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

 

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환하시오.

 

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

문제 풀이

import heapq

def get_minimum_count_of_overseas_supply(stock, dates, supplies, k):
    answer = 0
    last_added_date_index = 0 #공장이 멈추지 않는 한 가장 마지막에 넣은 날짜의 인덱스
    max_heap = []

    while stock <= k: #현재 재고가 남은 날짜 보다 많게!
        while last_added_date_index < len(dates) and dates[last_added_date_index] <= stock: #루프를 돌다가 공장이 멈추지 않는 선에서 탈출
            heapq.heappush(max_heap, -supplies[last_added_date_index]) #-를 붙여야 max heap이 됨
            last_added_date_index += 1
            
        answer += 1
        heappop = heapq.heappop(max_heap) #최대값 뽑기
        stock += -heappop            

    return answer

 

*key point: 최소한의 횟수 → 최댓값부터 하나씩 받기 (기간 내에 stock이 모두 사라지지 않는 선에서) → heap을 이용(heapq 모듈로 쉽게 사용 가능)