[백준]1826 연료 채우기 #그리디#힙#정렬

1. 풀이

(1) 주유소의 위치를 기준으로 가까운 순으로 정렬을 한다.

(2) 현재위치에서 최대로 갈 수 있는 위치를 확인한다

  - 갈 수 있는 위치가 도착지점을 넘으면 -> 종료

  - 넘지 않으면 -> 갈 수 있는 위치까지의 주유소 중 가장 주유를 많이 할 수 있는 곳에서 주유

(3) 주유한 만큼 위치이동

(4) (2),(3)을 반복

 

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)