❓1826번 : 연료 채우기
〽️ 문제 요약
N개의 주유소 정보가 주어질 때 현재 연료 P로 주유소를 최소로 들려서 목적지 L까지 가는 경우의 주유소 방문 횟수를 구하면 되는 문제
🤨 접근법
보석 도둑 문제와 비슷한 힙으로 구현한 우선순위 큐를 활용해 그리디하게 해결하는 문제이다. 즉, 최선의 선택은 현재 위치에서 갈 수 있는 주유소 중 가장 연료를 많이 충전할 수 있는 곳을 가는 것이다. 이를 위해 보석 도둑 문제에서 익혔던 방식처럼 힙을 활용해보자.
주유소 정보를 거리 기준 최소 힙으로 받는다. 단순히 현재 위치에서 가장 가까운 주유소부터 판단해야되기 때문이다. 이제 현재 연로로 갈 수 있는 주유소의 정보를 충전할 수 있는 연료를 기준으로 최대 힙에 받는다. 마찬가지로 갈 수 있는 주유소 중 가장 연료를 많이 충전할 수 있는 주유소로 가기 위함이다.
이제 최대 힙에서 하나씩 pop해본다. 해당 주유소에 들렸다는 의미이다. 동시에 카운트를 진행하며 현재 연료에 더해준다. 이 과정을 목적지까지 거리만큼 연료를 모을 때 까지 반복한다.
만약 이 과정에서 갈 수 있는 주유소가 없다면, 즉, 해당 최대 힙이 비었다면 목적지 까지 현재 연료로 갈 수 없다는 뜻이므로 카운트를 -1로 바꿔주고 반복문을 탈출한다.
🔡 코드
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N = int(input())
gas_stations = [] # min heap
for _ in range(N):
heappush(gas_stations, list(map(int, input().rstrip().split())))
L, P = map(int, input().rstrip().split())
count = 0
can_visit = [] # max heap
while P < L:
while gas_stations and gas_stations[0][0] <= P: # 현재 연료로 갈 수 있는 주유소들
distance, gas = heappop(gas_stations)
heappush(can_visit, (-gas, distance))
if not can_visit:
count = -1
break
P -= heappop(can_visit)[0]
count += 1
print(count)가장 최상위 while문의 조건을 위와 같이 설정함으로써 현재 연료가 목적지까지 갈 수 있을 정도로 모이면 반복문을 탈출할 수 있도록 하였고, 그 아래 while문은 힙으로 그리디 문제를 풀기 위해 현재 상태에서 할 수 있는 선택 정보를 get하는 전형적인 패턴이다.
기본적으로 min_heap을 지원하는 heapq 모듈의 특성상 max_heap을 구현하기 위해 연료 변수에 -를 붙여 push/pop 하도록 하였다. 때문에 현재 연료(P)에 주유소에서 충전할 수 있는 연료량을 더할때 빼기 연산을 진행한다.
📚 고찰
이전 문제에서 풀어봤던 유형의 문제였기 때문에 해결 방법까지 쉽게 도달할 수 있었지만, 문제에서 고려하지 않아도 되는 현재 위치를 중점적으로 고려하는 바람에 모든 테스트 케이스를 통과하도록 구현하지 못했다. 문제의 본질을 파악하고, 위와 같이 간결하고 설명이 되는 코드를 짜도록 노력해보자.
