[Python] 백준 1826: 연료채우기

1826번: 연료 채우기 (acmicpc.net)

1826번: 연료 채우기

1. 거리순으로 정렬을 해준다.

2. 마을에 도착할때마다 연료를 최대힙으로 넣어준다.

3. 마을에 도착할때 연료가 부족하면 힙에 있는 연료를 높은순으로 넣어준다.

4. 힙의 길이가 0 이고 연료가 부족하면 -1을 출력한다.

import sys
import heapq

n = int(input())
info = [list(map(int, input().split())) for _ in range(n)]
arrive, fuel = map(int, input().split())
ans = 0
info.append([arrive, 0])
info.sort()
heap = []

for i in range(len(info)):
    if fuel - info[i][0] < 0:
        while heap:
            fuel += -heapq.heappop(heap)
            ans += 1
            if fuel - info[i][0] >= 0:
                break
    if len(heap) == 0 and fuel - info[i][0] < 0:
        ans = -1
        break
    else:
        heapq.heappush(heap, -info[i][1])

print(ans)