[ 백준 ][ 골드2 ] 1826번 - 연료 채우기 ( 파이썬 Python )

링크 : https://www.acmicpc.net/problem/1826

1826번: 연료 채우기

 

문제

---

 

코드

---

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을 출력한다.