[백준 알고리즘] 1826번: 연료 채우기

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)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

출력

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

풀이

그리디 접근으로 푸는 문제였다. 처음에는 갈 수 있는 가장 긴 거리까지 계속 이동하게하면 될 줄 알았는데, 질문게시판을 보니 그렇게 하면 안되는 경우가 있었다.

2
2 3
4 7
14 4

위와 같은 입력이 주어졌을 때, 2번과 4번 주유소를 모두 거쳐서 목적지로 가게되면 총 연료가 14가 되므로 목적지에 도착이 가능한데, 항상 계속 긴 거리로 가려고 하면 시작연료가 4이기 때문에 2번 주유소를 건너뛰고 바로 4번 주유소로 가게된다.

따라서 이 문제에 대한 다른 접근이 필요하다. 해결책은 위 접근에서 하나의 조건을 더 더하는 것이다. 일단 현재 연료로 방문할 수 있는 모든 주유소 중에서 연료량이 가장 많은 주유소에 들린다. 동시에 드릴 수 있는 다른 주유소들도 체크해둔다. 그렇게 얻은 연료를 가지고 다시 방문할 수 있는 모든 주유소 중 연료량이 가장 많은 주유소에 방문한다. 이렇게 했을 때, 목적지에 도달하지 못하면 방문하지 않았지만 체크해둔 주유소를 확인해서 연료량이 많은 순서대로 들리도록 해본다. 목적지에 방문할 수 있는 연료가 채워지면, 추가한 주유소까지 포함해서 방문한 모든 주유소의 개수를 출력하고, 모든 주유소를 다 들리는 것을 가정했지만 목적지까지 갈 수 있는 연료량이 채워지지 않는다면 -1을 출력한다.

위 알고리즘을 구현하기 위해서 우선순위 큐를 사용하는 것이 용이하다. 현재 연료로 방문할 수 있는 모든 주유소를 우선순위 큐에 넣어두고, 실제로 방문할 때는 우선순위큐에서 연료량이 가장 큰 주유소만 들린다. 우선순위 큐에는 아직 방문할 수 있는 주유소가 남아있지만 방금 업데이트한 연료량으로 갈 수 있는 모든 주유소를 우선순위 큐에 넣는다. 그리고 실제로 방문할 주유소는 이전에 큐에 넣었던 주유소까지 모두 포함해서 연료량이 가장 많은 주유소에 방문한다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct Compare
{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        return a.second < b.second;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int N;
    cin >> N;

    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
    vector<pair<int, int>> stations;
    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;
        stations.push_back({a, b});
    }

    sort(stations.begin(), stations.end());

    int L, P;
    cin >> L >> P;

    int currFuel = P;
    int stationCount = 0;
    while (currFuel < L)
    {
        for (auto iter = stations.begin(); iter != stations.end() && !stations.empty(); iter++)
        {
            if ((*iter).first <= currFuel)
            {
                pq.push(*iter);
                iter = stations.erase(iter);
                iter--;
            }
        }

        if (pq.empty())
        {
            cout << -1;
            return 0;
        }

        currFuel += pq.top().second;
        pq.pop();
        stationCount++;
    }

    cout << stationCount;
}