[ 1826 ] [ Greedy ] 연료 채우기

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

1826번: 연료 채우기

---

풀이 과정

---

1. 현재 가진 연료로 어떤 주유소를 들릴 수 있는지를 업데이트 해주는게 핵심
2. 현재 가진 연료로 마을까지 갈 수 없다면 주유소를 무조건 하나 이상 들려야 함. 
   1. 따라서, 방문할 수 있는 주유소를 따로 기름의 양을 기준으로 최대 히프에 넣어 관리한다. 
   2. 이 때, 방문할 수 있는 주유소들 중 기름을 가장 많이 넣을 수 있는 주유소를 하나 방문해서 들려준다. 즉, 최대 히프에서 하나의 요소를 꺼내서 기름을 채워준다. 이 때 해당 주유소를 들리게 되므로 따로 카운트를 하나 늘려준다.
   3. 주유소를 방문해서 기름을 넣었으므로 넣은 기름으로 더 이동해서 방문할 수 있는 주유소를 다시 최대 히프에 넣어준다.
3. 방문할 수 있는 주유소가 더이상 없는데 마을에 도착하지 않았다면 -1을 리턴해 주고, 마을에 도착하였다면 방문한 주유소의 수를 출력시켜 준다.

---

소스 코드

---

import sys
import heapq
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
stations = [list(map(int, input().split())) for _ in range(N)]
dist, current_gas = map(int, input().split())
heap = []

stations.sort(key=lambda x:x[0])
queue = deque(stations)

answer = 0
while True:
    while queue and queue[0][0] <= current_gas:
        _, gas  = queue.popleft()
        heapq.heappush(heap, -gas)

    if dist <= current_gas:
        break
    else:
        if not heap:
            answer = -1
            break
        append_gas = -heapq.heappop(heap)
        current_gas += append_gas
        answer += 1

print(answer)