BOJ_1826 연료 채우기 C++

HDuckkk·2023년 4월 24일

Beakjoon Online Judge

목록 보기

8/13

BOJ 1826 연료 채우기

문제
성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.
그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.
정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

풀이과정

이 문제의 요점은 ”어떻게 최소한의 횟수로 주요소를 들러서 마을까지 갈 것인가?”입니다.

이 문제를 해결하기 위해 저는 다음과 같은 사고과정을 거쳤습니다.
바로 갈 수 있는 거리까지의 주유소를 모두 넣어가면서 가장 많은 연료를 갖는 주유소를 하나씩 이용하는 것 입니다. 글로 이해하려 하면 어려우니 예제를 통해 알아보도록 합시다.

위는 백준 문제에 나와있는 예시와 동일합니다. 검은색의 숫자가 주유소의 위치, 파란색의 숫자가 담을 수 있는 연료의 양 입니다. 또한 문제에서 처음에 들어있는 가스의 양이 10으로 정해져있습니다. 그럼 다음과 같은 사고를 할 수 있습니다.

현재 최대 갈 수 있는 거리가 10이며 이 이상 갈 수 없으니 지나오면서 들를 수 있었던 주유소 중 가장 많은 기름을 갖고 있는 주유소를 들른다고 생각하는 겁니다. 이러한 과정으로 계속 이어 나간다면 다음과 같아질 것입니다.

최종적으로는 29의 거리를 달렸으며 3개의 주유소를 들렸다는 것을 알 수 있습니다.

그렇다면 이러한 절차를 수행하기 위해서 코드로는 어떻게 작성해야 하는지 알아보도록 하겠습니다.

Solution

void solution(){
    INIT(); // 초기화
    int loc = startFuel;

    int cnt = 0;
    bool flag = true;
    while (loc < length){
        while (vec[vec.size()-1].first <= loc && !vec.empty()){
            q.push(vec[vec.size()-1].second);
            vec.pop_back();
        } // 일단 갈 수 있는 주유소 다 넣어.

        if(!q.empty()){
            loc += q.top();
            q.pop();
            cnt++;
        }else{
            cout << -1 << "\n";
            flag = false;
            break;
        }
    }

    if(flag){
        cout << cnt << "\n";
    }
}

우선 저의 경우에는 벡터와 우선순위 큐를 이용하여 구현했습니다. 우선 벡터에 주요소의 정보(위치, 연료량)을 입력한 뒤 주유소의 위치에 대하여 내림차순 정렬을 합니다. 내림차순 정렬을 하는 이유는 거리에 따라 뒤에서부터 벡터를 pop해가며 우선순위 큐에 넣어주기 위함입니다.

예를 들어 처음에 갈 수 있는 거리가 10이니 4와 5에 위치한 주유소를 pop한 이후 연료량 정보를 우선순위 큐에 넣어 가장 큰 연료량을 갖는 원소를 우선순위로 둘 수 있도록 했습니다.

이후 while문에서 현재 위치가 마을보다 작을 동안 반복하도록 한 뒤 벡터를 pop하여 우선순위 큐에 넣은 위 현재 위치를 가장 큰 연료량 만큼 계속 더해가며 수행하도록 했습니다.

이때 현재위치가 마을보다 적은데 큐가 비어버리면 갈 수 없다는 뜻 이므로 -1을 출력하도록 했습니다.

총 코드

// BOJ 1826
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;

vector<pii> vec;
priority_queue<int> q;
int N, length, startFuel;
void INIT(){
    cin >> N;
    for(int i=0; i<N; i++){
        int _location, _fuel;
        cin >> _location >> _fuel;

        vec.push_back({_location, _fuel});
    }
    sort(vec.begin(), vec.end(), greater<>()); // location 기준 오름차순 정렬

    cin >> length >> startFuel;

    // for(int i=0; i<N; i++){
    //     cout << vec[i].first << " " << vec[i].second << " "; 
    // }
}

void solution(){
    INIT();
    int loc = startFuel;

    int cnt = 0;
    bool flag = true;
    while (loc < length){
        while (vec[vec.size()-1].first <= loc && !vec.empty()){
            q.push(vec[vec.size()-1].second);
            vec.pop_back();
        } // 일단 갈 수 있는 주유소 다 넣어.

        if(!q.empty()){
            loc += q.top();
            q.pop();
            cnt++;
        }else{
            cout << -1 << "\n";
            flag = false;
            break;
        }
    }

    if(flag){
        cout << cnt << "\n";
    }
}

int main(){

    solution();

    return 0;
}