[ 백준 ][ 골드2 ] 1826번 - 연료 채우기 ( 파이썬 Python )
링크 : 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 as hq
import sys
input = sys.stdin.readline
n = int(input())
station = []
for _ in range(n):
hq.heappush(station,list(map(int,input().split())))
l,p = map(int,input().split())
cnt = 0
store = []
while p < l:
while station and station[0][0] <= p:
a,b = hq.heappop(station)
hq.heappush(store,(-b,a))
if not store:
cnt = -1
break
b,a = hq.heappop(store)
p += (-b)
cnt += 1
print(cnt)
풀이
이번 14기 소프트웨어 마에스트로 2차 코딩테스트의 2번 문제의 모티브가 되었을법한 그리디 문제이다.
여기서는 시간에 따라 충전되는 기능없이 단순히 현재 도달가능한 주유소 중 가장 많이 충전이 가능한 주유소를 골라가면 된다.
하지만 문제가 하나 있었다.
2
2 3
4 7
14 4
질문 게시판에 나온 반례인데 만약 현재 도달가능한 주유소 중 가장 많이 충전이 가능한 주유소만 골라서 가게 된다면 주유소(4)로가서 기름이 기름7(4-4+7)이되어 마을(14)까지 도달하지 못하게 된다.
이 문제를 해결하기 위해서는 가장 많이 충전이 가능한 주유소를 제외한 다른 주유소들도 저장하고 고려해야 하며 현재의 기름으로 다른 주유소나 도착지에 갈 수 없는 경우 그 주유소들을 방문해야 한다.
이 방법을 구현하기 위해 최대 heap 자료구조를 사용했다.
최대 heap에 현재 내가 갈 수 있는 거리안에 있는 모든 주유소를 저장한다.
이 때, 최대힙을 만들기 위해 주유소에서 충전가능한 기름의 양을 음수로 바꾸어 맨 앞에 저장한다.
현재 내가 갈 수 있는 거리가 마을까지의 거리 이상이 될 때까지 heappop을 수행한다.
여기서 pop되는 주유소는 현재 내가 갈 수 있는 가장 많은 기름을 주유소이다.
이렇게 지나쳐버린 주유소들까지 모두 고려하여 기름을 얻어갈 수 있게 된다.
만약 더 이상 방문할 주유소가 없는데 마을에 도달하지 못하면 -1을 출력한다.