[python] 백준 1826 연료 채우기

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

1826번: 연료 채우기

 

문제 해결

• 처음에 재귀(recursion)를 이용해 풀려고 했다.
• 하지만 모든 경우의 수를 다 찾아보는 것은 불필요하고 recursionError가 뜨게 되었다.
• 힙을 이용해 문제를 풀 수 있다고 하는데 어떻게 풀어야할지 몰랐다.
• 다른 분들의 풀이를 참고하여 풀 수 있게 되었다.
• 바로 계속 지나간다고 가정하고 만약 기름이 부족하게 되면 기름을 채우고 나서~채우기 전까지 지나간 주유소 중 가장 기름을 많이 채울 수 있는 곳에서 기름을 채우고 간다고 생각하면 되는 것이다. 물론 더 부족하면 그 다음 주유소 중 가장 기름을 많이 채울 수 있는 곳에서 기름을 또 채우고... 지나간 주유수에서 채울 수 있는 주유량을 리스트에 저장후 heap을 통해서 꺼내는 것이다.
• 하지만 큰 값을 꺼내야 하므로 (-)를 붙힌 후 저장을 하고 꺼낼 때 (-)을 붙여서 계산을 하면 된다.
• 코테를 보면서 비슷했던 유형이 있었던 것 같다. (미리 풀어봤으면 좋았을 뻔...)

 

CODE

import sys
input = sys.stdin.readline
import heapq

def solve(now,soil,cnt):
    h = []
    for i in range(n+1):
        d = S[i][0] - now
        now = S[i][0]
        if soil<d: # 주유소를 안지나다녔을 때 막히는 부분
            while soil <d:
                if len(h)>0:
                    soil += (-1*heapq.heappop(h)) # 기존에 지나쳤던 곳 중 많이 주유할 수 있는 것부터 채운다.
                    cnt += 1
                else:
                    cnt = -1
                    break
            if cnt == -1: break
        soil -= d
        heapq.heappush(h,-1*S[i][1]) # 주의해야할 것이 주유소를 지나가다가 주유가 부족해서 기존의 지나쳤던 곳 중 많이 주유할 수 있는 곳에서 주유를 했지 부족한 지점에서 주유를 한 것이 아니다. 따라서 부족한 곳에서 주유를 한 것이 아니기 때문에 그냥 지나간다 생각하고 h에 저장하여 나중에 부족하면 꺼내서 쓰거나 하는 것이다.
    return cnt
        


if __name__=='__main__':
    n = int(input())
    S = []
    for _ in range(n+1): # 종착역 까지 저장
        x = tuple(map(int, input().split()))
        S.append(x)
    S.sort()
    p = S[-1][-1] # 처음 가지고 있는 연료량
    cnt = 0
    ans = solve(0,p,0) # 현재 위치, 가지고 있는 연료량, 들린 주유소 수
    print(ans)