백준 1826 연료 채우기

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

내가 처음 문제를 접근한 방법은 일단 좌표위에 주유소들을 그려놓고 차를 이동하는 것을 시뮬레이션 하였다.

시뮬레이션을 하다보면 주유소를 방문하는데, 이때 2가지로 나눌 수 있다.
해당 주유소를 방문을 하냐/안하냐로 나눌 수 있다.
그러면 다음 주유소에서도 이와같이 두가지로 나눌 수 있는데 문제점은 주유소 방문의 분기의 판단지점이 미래의 주유소들의 거리와 관계가 있다는 것이다.
결국 위와 같은 접근방식은 어떤 지점까지 가는데, 여기서 주유를 했어야 했네와 같은 문제점이 생기며 이는 이전 인덱스를 다시한번 접근해야하는 문제가 생긴다.

그래서 접근 방법을 다음과 같이 바꾸었다.
일단 목적은 마을에 도착하는 것이고, 차를 가능한 최대한 움직여보자. 최대한 움직였는데 다음 주유소 까지 기름이 없다면 현재 위치보다 이전에 있는 주유소에서 주유를 했어야 했네하고 해당 주유소를 체크하는 것이다.
잘 생각해보면 체크하는 방식에서 n크기 만큼 배열을 만드는 것이 아닌, 힙을 쓰는 방법이 유리하다. 그 이유는 차를 일단 움직여 놓고, 그 이전에 주유소들중 최대한 많은 기름을 주는 주유소를 선택하기 때문에 해당 주유소가 어디에 있던 중요하지 않다.

위의 로직을 코드로 옮기면 다음과 같다.

import heapq
n = int(input())
stations = []
heap = []
for i in range(n):
    a,b = map(int,input().split())
    stations.append([a,b])
stations.sort(key = lambda x:x[0])
v = list(map(int,input().split()))
start = v[1]
end = v[0]
idx = 0
ans = 0
while start < end:
    while idx < n and stations[idx][0] <= start:
        a,b = stations[idx]
        heapq.heappush(heap,-b)
        idx += 1
    if heap:
        b = heapq.heappop(heap)
        start += -b
        ans += 1
    else:
        ans = -1
        break
print(ans)