[백준] 1826 연료 채우기 (C++)

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

문제

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 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)은 성경이의 위치에서 마을까지의 거리, P(1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

모든 주유소와 마을은 서로 다른 좌표에 있고, 마을은 모든 주유소보다 오른쪽에 있다.

---

풀이

그리디로 생각하면 쉽게 풀 수 있는 문제이다.

만약 주유소를 방문하는 모든 경우의 수를 계산하게 된다면 주유소 1만개의 모든 조합을 생각해야 하기 때문에 매우 비효율적이다.

이를 우선순위 큐를 활용하여 최소한의 주유소를 방문하며 최대한 이동할 수 있는 거리를 순차적으로 계산하면 해결할 수 있다.

 

먼저 주유소의 위치를 오름차순으로 정렬한다.

예제 입력 1에는 주유소의 위치가 오름차순으로 주어지지만, 이는 조건에 명시되어있지 않아 정렬을 해주어야 한다.

 

이후에는 자동차에 저장된 연료만큼 이동을 진행한다.

처음에는 P만큼의 연료가 있으므로 P까지 이동할 수 있을 것이다.

그리고 P까지 이동했다는 것은 0~P 사이에 있는 주유소를 방문 할 수 있음을 의미한다.

따라서 우선순위 큐에 0~P 사이에 있는 모든 주유소 a에서 채울 수 있는 연료의 양, b를 push한다.

 

하지만 우리는 P까지 이동하였을 뿐, 마을에 도착하지 못하였을 수 있다.

마을까지 이동하기 위해서는 주유소에 들러 연료를 채워야 하는데, 이 때 우선순위 큐에 저장된 연료의 MAX값 b를 pop하여 더한다.

그러면 P+b 위치까지 이동할 수 있을 것이고,

다시 우선순위 큐에 P+1~P+b 사이에 있는 주유소에서 채울 수 있는 연료를 우선순위 큐에 추가한다.

위 과정을 반복하면 마을까지 이동하기 위한 최소 주유소 방문 횟수를 구할 수 있다.

만약 우선순위 큐가 비어있는데 마을에 도착하지 못하였다면, -1을 출력해주면 된다.

 

예제 입력 1의 경우는 다음과 같다.

 

1.

현재 위치: 10 (최초에 저장된 연료 10만큼 이동)

우선순위 큐: [4,  2] (위치 4, 위치 5에 있는 연료 추가)

주유소 방문 횟수: 0

 

2.

현재 위치: 14 (4만큼 이동)

우선순위 큐: [5, 2] (위치 11에 있는 연료 추가)

주유소 방문 횟수: 1

 

3.

현재 위치: 19 (5만큼 이동)

우선순위 큐: [10, 2] (위치 15에 있는 연료 추가)

주유소 방문 횟수: 2

 

4.

현재 위치: 29 (10만큼 이동)

우선순위 큐: [10, 2] (위치 25에 있는 연료 추가)

주유소 방문 횟수: 3

 

4에서 마을의 위치인 25에 도착하였으므로 주유소에 방문하는 최소 횟수는 3이다.

코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

pair<int, int> oils[10000];

int main(){
    int n;
    cin >> n;

    for (int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        oils[i] = {a, b};
    }

    int l, p;
    cin >> l >> p;

    sort(oils, oils+n);

    priority_queue<int> pq;
    int cur = 0;
    int oilIdx = 0;
    int answer = 0;


    cur += p;
    while (oilIdx < n && oils[oilIdx].first <= cur){
        pq.push(oils[oilIdx].second);
        oilIdx++;   
    }
    while (!pq.empty() && cur < l){
        p = pq.top();
        pq.pop();
        answer++;

        cur += p;
        while (oilIdx < n && oils[oilIdx].first <= cur){
            pq.push(oils[oilIdx].second);
            oilIdx++;   
        }
    }

    if (cur >= l){
        cout << answer;
    }
    else{
        cout << -1;
    }

}