문제
성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.
그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.
정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.
내 코드
import heapq
import sys
from collections import deque
sys.stdin = open("input.txt", "rt")
# 1km 가는데 1L의 연로가 필요
# 주유소 n개 존재
# 주유소에서 멈추는 횟수 최소화
# 각각의 주유소의 위치와 각 주유소에서 얻을 수 있는 연료의 양이 주어진다
# 주유소에서 멈추는 횟수 구하기 -> 가장 최소로 멈춰야 함
# 1. 시작점에서 도착점까지 필요한 연료
# L : 성경이의 위치에서 마을까지의 거리 P : 트럭에 원래 있던 연료 양
n = int(input())
data = []
for _ in range(n):
a,b = map(int, input().split()) # 시작위치에서 현재 주유소까지 거리, 채울 수 있는 연료 양
data.append((a,b))
L,P = map(int, input().split())
# 마지막 주유소 통과했을 때 검사하기 위해 도착점을 추가해줌.
data.append((L,0))
data.sort(key = lambda x : x[0]) # 거리 기준 오름차순
if P >= L:
print(0)
exit(0)
# n <= 10,000 => n^2 가능
dq = deque(data)
cnt = 0
heap = []
for loc, power in data: # 하나씩 위치, 채울 수 있는 연료량 꺼내서
if P >= L:
break # 가능한 경우 끝
while P < loc and heap: # 현재 연료로(위치로) 해당 주유소(loc,power) 못간다면
# 현재까지의 주유소 중 가장 최대의 연료량을 꺼내서 넣어주기
P += -heapq.heappop(heap)
cnt += 1 # 넣어주면 해당 주유소 들린 거니깐 추가
if P < loc: # 위 과정을 거쳤는데도 현재 주유소에 못간다는 것은 도달 못한다는 것.
break
heapq.heappush(heap, -power) # 주유소 우선순위 큐에 넣어두기 (어차피 거리순 정렬이라서 가능한 경우부터 만나게 된다.)
if P >= L:
print(cnt)
else:
print(-1)코멘트
문제를 그리디하게 풀 생각 했어야 함.
P로 다음 주유소에 도착했을 때 만약 주유소의 거리가 P보다 크다면, 이때는 주유를 해야하는 상황으로 인식.
이미 주유한 주유소를 제외하고 가장 주유량이 큰 주유소에서 연료를 공급받아야 한다.
즉, 우선순위 큐(힙)을 사용하면 편하다.
주유소까지의 거리를 만족할 때까지 우선순위 큐에서 주유 연료량을 pop하고, 모든 과정 뒤에는 현재 주유소의 연료량을 큐에 삽입한다.
만약 모든 우선순위 큐의 주유량을 썼음에도 다음 주유소에 도달하지 못한다면 (안되는 경우) -> -1 출력.
마지막 주유소를 통과했을 때 해당 트럭이 마을에 도달할 수 있는지 (도착점을 검사해야 한다.) -> (마을좌표,0)의 데이터를 추가적으로 삽입하였다.
그리디 + 우선순위 큐 -> 거리순, 주유량 순으로 정렬하고 진행
가장 핵심적인 풀이 아이디어는
현재 위치에서 다음 주유소까지 갈 수 없다면, 우선순위 큐에서 가장 큰 연료량을 꺼내 보충해야 한다.
주유소에 도착했다면 해당 주유소의 연료량을 우선순위 큐에 추가.
