https://www.acmicpc.net/problem/1826
1826번: 연료 채우기
첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경
www.acmicpc.net
import heapq
import sys
N = int(sys.stdin.readline())
gas_stations = []
for _ in range(N):
a, b = map(int, sys.stdin.readline().rstrip().split())
heapq.heappush(gas_stations, (a, b))
remain_distance, remain_gas = map(int, sys.stdin.readline().rstrip().split())
ans = 0
stop_stations = []
while remain_gas < remain_distance:
while gas_stations and gas_stations[0][0] <= remain_gas:
distance, gas = heapq.heappop(gas_stations)
heapq.heappush(stop_stations, (-gas, distance))
if not stop_stations:
ans = -1
break
remain_gas -= heapq.heappop(stop_stations)[0]
ans += 1
print(ans)
7-8개월 전 쯤 한번 풀었던 문제다.
우선, 이 문제의 핵심은 아이디어는 이렇다.
1. 현재 보유하고 있는 기름으로 갈 수 있는 주유소 중 가장 많은 기름을 주는 곳을 가는 것.
2. 주유소에 들를때마다 보유 기름을 변경하고, 남은 거리를 재계산 하는 것이 아니라 내가 보유한 기름 총량(기본보유 기름 P + 주유소에서 주유한 기름)으로 목적지까지의 거리 (L) 를 갈 수 있는지 계산하는것.
주유소에 들를때마다 보유 기름을 변경하고, 남은 거리를 재계산 해도 풀 수는 있겠지만 구현이 굉장히 복잡해지고 어려워진다.
풀이 과정.
1. 주유소를 거리순 으로 최소힙(gas_stations)에 담는다.
2. 현재 내가 보유한 기름으로 목적지에 도달할 수 없으면 순회한다. (첫번째 while)
-> 최초로 주어지는 기름 보유량 P로 목적지에 도달할 수 있으면 순회할 필요가 없기때문에 바로 순회없이 while 이후문이 실행되어 0이 출력
3. 현재 보유한 기름으로 갈 수 있는 주유소만큼 순회한다. (두번째 while)
4. 각 주유소의 주유가능한 연료순으로 최대힙(stop_stations)에 담는다.
-> 최대힙으로 만들기 위해 연료를 음수로 저장한다
5. 최대힙(stop_stations) 에 값이 없다면 현재 보유 기름으로 더이상 갈 수 있는 곳이 없다는 뜻이므로 결과에 -1 을 저장한 후 while 으로 종료한 후, 출력한다.
6. 최대힙(stop_stations) 에 값이 있다면 pop 한다. stop_stations 는 최대힙이므로 팝했을 때 가장 큰 수가 나온다. 즉, 내가 보유한 기름으로 갈 수 있는 주유소 중 가장 많이 주유할 수 있는 연료가 나온다.
7. 내가 보유한 기름으로 갈 수 있는 주유소 중 가장 많이 주유할 수 있는 연료를 내가 보유한 기름에 누적한 다.
8. 들른 주유소. 즉, 결과에 1을 더한다.
9. 이 과정을 반복한다.
10. 결과를 출력한다.