문제
성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.
그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.
정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.
입력
첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.
출력
첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.
import heapq
n = int(input())
gs = []
#최소힙
for _ in range(n):
dist,f = map(int,input().split())
heapq.heappush(gs,[dist,f])
#최대힙
target,fuel = map(int,input().split())
filled = []
cnt = 0
#종료조건: 종점과 fuel이 같아지거나 fuel이 더 커졌을 때
while target>fuel:
#현재 fuel로 갈 수 있는 거리의 gas들을 최소힙에서 빼내서 전부 move라는 최대힙에 넣음
while gs and gs[0][0]<=fuel:
dist, f = heapq.heappop(gs)
# -1을 곱해주어서 최대힙으로 사용
# 최대힙에 넣는 이유는 문제에서 주유소에서 멈추는 횟수를 최소화하라고 하기 때문에, 가능한한
# 기름을 많이 채울 수 있는 주유소에서 채우기 위함
heapq.heappush(filled,-1*f)
#주유소에서 기름을 다 채웠거나, 아니면 주유소는 남았는데 현재 fuel로 해당 주유소들에 도달할 수
#없을 경우에는 종점까지 못 가므로 -1을 print하고 종료
if not filled:
cnt = -1
break
#최대힙에서 빼낸 기름을 현재 fuel에 더해주고, 주유소에 멈췄으므로 count
f = heapq.heappop(filled)
fuel += -1*f
cnt+=1
print(cnt)
접근방식은 맞게 떠올렸는데도 쉽게 구현하지 못했다.
우선순위 큐가 머릿속에 떠오르니 않아서, 이를 사용하지 않고 풀려니 구현이 복잡해졌었다.
구글링 해서 다른 사람들이 푼 해설을 보고, 이해해서 다시 내 코드로 구현해봤다.
개념을 이해하고 쉬운 문제 사용해보는 것을 넘어서, 다양한 케이스에 적용하는법을 경험해보고 익숙해져야할것같다.
