[백준]1826 연료 채우기

1. 풀이

(1) 현재 가지고 있는 기름으로 방문가능한 모든 주유소 중에 가장 기름을 많이 넣을 수 있는 주유소를 후보에 추가한다. 

(이때 후보주유소는 힙으로 관리한다. 게속 추가하고 매회 최댓값을 추출해야 하기 때문)

• (2) 후보(heap)에서 최댓값을 추출한다. 

(이때 방문횟수를 +1)

* 만약 방문할 주유소가 없으면 답은 -1

 

2. 소스코드

import heapq
import sys
from collections import deque

N=int(input())
point=[]
for i in range(N):
    a,b=map(int,sys.stdin.readline().rstrip().split())
    point.append([a,b])
L,P=map(int,input().split())

point.sort()
point=deque(point)
oil=P
ans=0
shopPQ=[]
while(1):
    # 마을도착하면 그만
    if oil>=L:
        break
    # 도착못하면 주유소에 서기
    else:
        # 후보주유소 추가
        while(point):
            loc,addedOil=point.popleft()
            if loc<=oil:
                heapq.heappush(shopPQ,-1*addedOil)
            else:
                point.appendleft([loc,addedOil])
                break
        # 범위안에 최대충전량 더하기
        if shopPQ:
            added=heapq.heappop(shopPQ)
            added*=-1
            ans+=1
            oil+=added
        else:
            ans=-1
            break

print(ans)