[백준] 1826. 연료채우기 (Python)

백준 1826번 문제, 연료채우기

1826번: 연료 채우기

골드 3

---

문제

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

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

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

 

입력

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

 

출력

첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.

 

---

일직선상의 정글에서, 주유소를 최소로 들르면서 목적지까지 이동할 수 있는 방법 구하기.

다행히도 새는 연료만 있고, 주행에 필요한 연료를 별도로 계산할 필요는 없어서

거리 1당 1의 기름만 빼주면 되는 문제!

 

그리디 문제는 항상 풀 때마다,

'이렇게 순간 순간 최선을 선택하는게 결과적으로 최선이 된다고!!!? 그럴리 없어' 하는 의문이 든다.

그럴 때는 놓칠 것 같은 입력값을 열심히 고민해보고, 모든 케이스를 커버하는 그리디 조건인지 차분히 확인해보자.

그치만 급할 때는 대충 의문을 누르고 넘어가자^^

 

갈 수 있는 주유소가 여러 개 있을 때, 가장 최소로 주유소를 들러야 한다면,

당연히 주유할 수 있는 기름 양이 많은 주유소를 먼저 선택해야한다.

는 그리디 조건을 가지고 코드를 구현해보자.

 

갈 수 있는 주유소, 주유 가능한 기름 양을 담은 리스트에서 항상 가장 큰 수를 뽑을 것이므로!!

-> 힙(heap)을 사용해준다.

(큰 걸 먼저 뽑아야 하니까, 값에 -를 붙여 우선순위를 지정해주면 된다.)

 

 

현재 성경이의 위치를 0이라고 보고, 주어진 입력에 따라 그림을 그려보면 위와 같다.

 

현재 가지고 있는 기름이 10이므로 10을 써서 갈 수 있는 주유소들을 보면

4, 5 위치에 있는 주유소 2개를 갈 수 있고, 그 주유소들에서 주유 가능한 기름 양을 보면

 

4와 2다!

이 4와 2를 힙에 넣는다.

 

그리고 가장 큰 값을 꺼내 그 기름만큼 이동한다.

이미 주유한 4는 빼고, 주유 가능한 기름 리스트는 2, 5

 

새로 추가된 5를 힙에 넣어주고 가장 큰 값을 뽑으면 -> 5

 

5만큼 또 이동하고,

또 추가된 주유소의 기름양을 힙에 넣어주고,

최댓값을 꺼내 주유해주고, 그만큼 이동하면!

 

이번에는 갈 수 있는 거리가 도착지점의 좌표를 넘었기 때문에 

탐색을 종료한다!

 

총 3개의 주유소를 들렀으므로, 3 출력.

 

최대한 다 주유해도 도착을 못하는 경우는 -> 힙이 비어있는데 도착지점에 도착못했을 때.

 

위 내용대로 구현을 해주면,

import heapq


if __name__ == "__main__":
    N = int(input())
    gas_station = list()
    for i in range(N):
        idx, oil = map(int, input().split())
        gas_station.append([idx, oil])

    gas_station.sort(key=lambda x: x[0])
    distance, cur_oil = map(int, input().split())

    answer = 0
    can_go = 0
    can_go += cur_oil
    oil_heap = list()

    while can_go < distance:     #현재 위치 + 가진 오일이 목적지를 넘기 전까지만 확인
        answer += 1
        while gas_station:
            if gas_station[0][0] <= can_go:
                tmp = gas_station.pop(0)
                heapq.heappush(oil_heap, (-tmp[1], tmp[1])) 
                #내림차순 정렬을 위해, -tmp[1] 값으로 우선순위를 지정
            else:
                break

        if not oil_heap:
            answer = -1
            break

        tmp_oil = heapq.heappop(oil_heap)
        can_go += tmp_oil[1]

    print(answer)

이와 같다!

 

 

부족한 설명에 대해서는 질문을 남겨..주세요..😋