이번 문제는 현재 가지고 있는 연료의 양으로 갈 수 있는 주유소 중에서 가장 많은 연료를 채울 수 있는 주유소에 방문하는 것을 기본으로 하여 해결하였다. 주유수의 정보를 모두 입력 받은 뒤에 이를 내림차순으로 정렬한 후 목적지에 갈 수 있는 기름이 모일 때까지 현재 기름으로 갈 수 있는 주유소에 대한 정보를 최대힙에 저장하여 가장 연료 충전량이 많은 것을 취하는 방식으로 구현하였다.

• heapq를 불러온다.
• n을 입력받는다.
• 주유소의 정보를 배열 stations에 입력받는다.
• 목적지의 위치에 해당하는 변수 goal과 초기에 가지고 있는 연료의 양을 저장하는 변수 cur_gas를 입력받는다.
• stations를 내림차순으로 정렬한다.
• 현재 기름으로 갈 수 있는 주유소의 충전량을 저장하는 배열 tmp를 선언한다.
• 주유소에 들리는 횟수를 나타내는 cnt를 0으로 정의한다.
• cur_gas가 goal보다 작을 동안 반복하는 while문을 돌린다.
  -> stations의 원소가 존재하고 stations[-1][0]이 cur_gas보다 작거나 같을 동안 반복하는 while문을 돌린다.
  --> 주유소의 위치에 해당하는 임시 변수 distance와 연료 충전량에 해당하는 임시 변수 gas를 선언하고 stations를 pop()하여 각각에 저장해준다.
  --> tmp에 heapq의 heappush를 이용하여 -gas를 넣어준다. -를 붙인 이유는 heapq.heappush()는 입력 시 오름차순으로 자동 정렬이 되기 때문에 -를 붙여 반대 순서, 즉 최대힙을 구현하기 위함이다.
  -> 만약 tmp가 비어있다면 while문을 탈출한다.
  -> cur_gas에 tmp를 heappop()하여 빼준다. -gas로 저장되어 있기 때문에 이는 곧 더하는 과정이 된다.
  -> cnt를 1 증가시킨다.
• 만약 goal이 cur_gas보다 작거나 같다면 cnt를 출력한다.
• 만약 goal이 cur_gas보다 크다면 -1을 출력한다.

Code

import heapq
n=int(input())
stations=[list(map(int, input().split())) for i in range(n)]
goal, cur_gas=map(int, input().split())
stations.sort(reverse=True)
tmp=[]
cnt=0
while cur_gas<goal:
    while stations and stations[-1][0]<=cur_gas:
        distance, gas=stations.pop()
        heapq.heappush(tmp, -gas)
    if not tmp:
        break
    cur_gas-=heapq.heappop(tmp)
    cnt+=1
if goal<=cur_gas:
    print(cnt)
else:
    print(-1)