연료 채우기

알고리즘 구분 : 그리디, 우선순위 큐, 정렬, 자료 구조

문제

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 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
4
4 4
5 2
11 5
15 10
25 10
예제 출력 1
3

문제 풀이

성경이의 트럭은 연료를 채울 때에 제한이 없다. 그렇기에, 연료 제한에 맞추어 선택하는 경우의 수를 생각할 필요가 없는 상황이다.
먼저 마을에 도착하지 못할 경우는 모든 주유소를 들려서 연료를 채워서 이동하여도 목적지까지 도달하지 못하는 경우이기에, 입력을 받을 때, 변수 하나를 별도로 활용하여 확인하도록 한다.

첫 번째 접근법은
현재 가지고 있는 연료량 안에서 도달할 수 있는 주유소 중 가장 많은 연료를 주입할 수 있는 주유소를 방문하는 과정으로 알고리즘을 구현하고자 했었다.

그러나 위 사진의 마지막 부분에 적혀있듯이, 현재 도달할 수 있는 주유소 중 여러 군데를 방문해야 하는 경우에 대한 처리가 불가능하다는 것을 깨달았다.

두 번째 접근법은
연료량이 가장 많은 주유소 순으로 정렬을 한 뒤에, 연료량이 가장 많은 주유소를 방문하지 못한다면 그 다음 연료량이 많은 주유소가 방문이 가능한지를 확인하는 과정을 반복하도록 했다.
구현하여 제출하였더니 MLE를 받았다.

세 번째 접근법은
1) 현재 위치에서 갈 수 있는 주유소들의 정보를 모두 우선순위 큐에 저장
2) 가장 많은 양의 연료를 충전할 수 있는 주유소를 들려서 연료 충전
3) 이후 충전한 이후 도달할 수 있게 되는 주유소들의 정보를 우선순위 큐에 저장
위의 과정 반복

소스 코드

정답 소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n, l, p;
vector<pair<int, int>> gas;
int solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        gas.push_back({a, b});
    }
    cin >> l >> p;

    cout << solve() << endl;

    return 0;
}

int solve() {
    int gasIdx, result; // gasIdx = 주유소 Idx, result = 주유소 들리는 횟수
    priority_queue<int, vector<int>, less<int>> pq;

    sort(gas.begin(), gas.end(), less<pair<int, int>>()); // 주유소 정렬

    gasIdx = 0;
    result = 0;

    while(p < l) {
        for(int i = gasIdx; i < n; i++) {
            if(gas[i].first <= p) {
                pq.push(gas[i].second);
            }
            else {
                gasIdx = i;
                break;
            }
        }

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

        p += pq.top();
        pq.pop();
        result++;
    }
    
    // 결과 반환
    return result;
}

MLE 소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n, l, p, check;
priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> gas;
int solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    check = 0;

    cin >> n;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        gas.push({b, a});

        check += b;
    }
    cin >> l >> p;

    // 모든 주유소를 들려 연료를 얻어도 해당 마을에 도착하지 못할 경우 조건문
    if(check + p < l) {
        cout << -1 << endl;
    }
    else {
        cout << solve() << endl;
    }

    return 0;
}

int solve() {
    int now, result; // now = 성경이 위치, result = 주유소 들리는 횟수

    while(now + p < l) {
        queue<pair<int, int>> temp; // 임시 저장소

        while(true) {
            pair<int, int> data = gas.top();
            gas.pop();

            if(now + p < data.second) {
                temp.push(data);
            }
            else {
                p = p + data.first - (data.second - now);
                now = data.second;
                break;
            }
        }

        while(!temp.empty()) {
            gas.push(temp.front());
            temp.pop();
        }

        result++;
    }
    
    // 결과 반환
    return result;
} 

• 문제 출처 : https://www.acmicpc.net/problem/1826
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.