(Python/파이썬) - 백준(BOJ) 1826번 : 연료 채우기

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

1826번: 연료 채우기

---

• 문제 : 

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.

 

그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.

 

정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

 

 

 

---

• 풀이 :

그리디 알고리즘과 힙을 사용하여 해결할 수 있는 문제였습니다.

 

84%에서 계속 틀렸습니다가 나와서 고통받았던 문제입니다.

 

고통의 흔적...

문제 해결 아이디어는 아래와 같습니다.

 

1. 주유소를 거리에 따라 오름차순 정렬해서 station 큐에 넣음 (큐를 사용한 이유는 거리가 작은순으로 사용하기 위함.

만약 내림차순 정렬했다면 stack의 기능을 하는 list를 사용했어도 됐을듯)

 

2. station이 있을 때 (남은 주유소가 있을 때) 가장 가까운 주유소의 거리가 현재 기름양인 P보다 작거나 같다면 최대힙에 넣음. 최대힙은 현재 연료로 갈 수 있는 주유소들의 정보이며 최대힙이기 때문에 충전할 수 있는 연료의 양 기준으로 내림차순 정렬되어있음

 

3. 최대힙에서 pop한 값을 P에 더하고 L보다 크거나 같다면 현재까지의 카운트를 출력. 아니라면 갈 수 있는 주유소를 탐색하는 부분부터 반복 실행.

 

추가 아이디어 )

84%에서 계속 틀린이유를 30분동안 고민했는데 해결해보니 진짜 바보같은 실수를 했습니다.

주어지는 L과 P에서 P가 L보다 항상 작다는 보장이 없기 때문에 처음부터 P가 L보다 크다면 바로 0을 출력해주어야 했습니다....

 

 

 

---

• 소스코드 : 

import sys
import heapq as hq
from collections import deque

input = sys.stdin.readline
N = int(input())
station = deque(sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x : (x[0],-x[1])))
L, P = map(int,input().split())
heap = []
answer = 0

if P >= L: # 시작부터 마을에 갈 수 있는 경우
    print(0)
    exit()

while True:
    while station: # 남은 주요소가 있는 경우
        if station[0][0] <= P: # 주요소를 갈 수 있는 경우
            hq.heappush(heap, -station.popleft()[1]) # 최대힙에 삽입
        else:
            break
    if heap: # 갈 수 있는 주유소가 있는 경우
        P += -hq.heappop(heap)
        answer += 1
        if P >= L: # 도착한 경우
            print(answer)
            exit()
    else: # 갈 수 있는 주유소가 없는 경우
        print(-1)
        exit()