[백준] 1826번 연료채우기

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

1826번: 연료 채우기

 

로직조차 생각이 잘 나지 않았던 문제

 

1. (연료의 위치, 채울 수 있는 연료의 양)을 리스트에 담아 연료 위치 순으로 sort한다.
2. heap에는 현재 연료양으로 지나갈 수 있는 위치들이 연료들을 최대힙으로 담는다. 
3. 만약 현재 연료양으로 지나갈 수 없는 위치라면, 그 이후는 다 지나갈 수 없으니까 일단 해결하고 봐야한다.
4. 그래서 while heap문으로 연료양을 채운다. (최대 연료양 순으로)
5. 만약 len(heap) == 0이라는 것은 더 이상 채울 연료가 없다는 뜻이므로 현재 가진 연료양 < 지나가야 하는 거리 이면 -1을 리턴한다.
6. 즉, for문을 돌면서 i 지점에서 연료를 채운다는 개념이 아니라, 그 지점을 지나갈 수 있게끔 heap에서 연료들을 꺼낸다는 개념이다. 

import sys
import heapq

n = int(sys.stdin.readline())
info = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
arrive, fuel = map(int, sys.stdin.readline().split())
info.append([arrive, 0])
info.sort()

heap = []
answer = 0

for i in range(n + 1):
    dist, plus = info[i]
    if fuel < dist:
        while heap:
            fuel += -heapq.heappop(heap)
            answer += 1
            if fuel >= dist:
                break
    if len(heap) == 0 and fuel < dist:
        answer = -1
        break
    else:
        heapq.heappush(heap, -plus)
print(answer)

 

 

https://lcyking.tistory.com/14

[Python] 백준 1826: 연료채우기