BOJ 1826: 연료 채우기 [Python 3]

import sys
input=sys.stdin.readline
import heapq
n=int(input())
data=[list(map(int,input().split())) for _ in range(n)]
location,p=map(int,input().split())
heapq.heapify(data)
possibleGas=[]
answer=0
while p<location:
    while data and data[0][0]<=p:
        heapq.heappush(possibleGas,-heapq.heappop(data)[1])
    if not possibleGas:
        answer=-1
        break
    p+=-(heapq.heappop(possibleGas))
    answer+=1
print(answer)

먼저 data에는 필요한 각 좌표에 주유소까지의 거리와 채울 수 있는 연료의 양을 input 받고, 이 데이터를 heap에 넣는다.

반복문을 돌면서, 아직 내가 도착할 수 있다면, (정확히 말해서 '내가 목표 지점을 넘을 수 있고, 더 이상의 주유소를 들리지 않아도 된다면')

data에서 주유소가 있고, 주유소까지의 거리가 현재 남아있는 연료로 갈 수 있다면,

'내가 들릴 수 있는 주유소' 리스트에 넣는다.

 

 

 

이제 주유소에 들려야 한다. ('들렸었어야 한다.')

'내가 들릴 수 있는 주유소'에서 제일 뽑아먹을 수 있는 연료가 큰 순으로 하나씩 뽑아낸다.

 

만약 내가 들릴 수 있는 주유소가 없으면, 완주가 불가능하므로, 반복문을 종료한다.

문제에서 준 예시이다.