[Python] boj no. 1826 : 연료 채우기

Problem

https://www.acmicpc.net/problem/1826

Idea

1km를 이동하기 위해 1L가 필요하므로 거리가 L인 마을에 도착하기 위해서는 가스가 L 이상이여야 한다. 주유소에서 멈추는 횟수를 최소화하기 위해서는 연료가 필요할 때마다 이전에 방문했었던 주유소 중에서 가장 많은 양을 제공받는 순으로 멈추면 된다.

1. 도착지를 주유소 리스트에 포함한 뒤 거리에 대해 오름차순으로 정렬한다. 이 때, 도착지는 제공 연료량을 0으로 둔다.
2. 주유소 리스트를 탐색하여 연료로 해당 주유소까지 방문할 수 있을 경우 연료량을 최대힙에 추가한다.
3. 해당 주유소까지의 거리보다 연료가 부족할 경우, 연료가 충분해질 때가지 최대힙으로부터 많은 순서로 연료를 얻는다. 이 때, 주유소에 들린 횟수를 1만큼 증가시킨다.
4. 연료를 제공받은 이후에도 부족할 경우, 해당 주유소에 도착할 수 없으므로 -1을 반환한다.
5. 연료량이 L보다 클 경우, 마을에 도착할 수 있다.

Code

import sys
import heapq

input = sys.stdin.readline

N = int(input())
station = []
for _ in range(N):
    station.append(tuple(map(int, input().split())))
L, P = map(int, input().split())
station.append((L, 0))
station.sort(key=lambda x:x[0])

sol = 0
heap = []
for dist, gas in station:
    if P >= L:
        break
    
    if P < dist:
        while heap and P < dist:
            g = heapq.heappop(heap)
            P += -g
            sol += 1

    if P < dist:
        sol = -1
        break
    else:
        heapq.heappush(heap, -gas)

print(sol)

Comment