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

문제

1826번: 연료 채우기

풀이

그리디, 정렬, 우선순위 큐

 

✔ 정답 코드 1

• 연료가 높은 주유소가 top에 위치하도록 우선순위 큐에 넣는다.
• 우선순위 큐를 top에서 부터 방문하며, top이 현재 방문할 수 없는 주유소라면 벡터에 넣는다. 
• 현재 방문할 수 있는 주유소가 top에 위치하였을 때, P에 더하고 벡터에 있는 값들을 다시 우선순위 큐에 넣는다. 
• 이를 P가 L 이상일 때까지 반복

이렇게 하면 다음 방문할 주유소를 탐색할 때, 우선순위 큐를 처음부터 다시 돌아야 해서 시간이 많이 걸렸다. 

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

using namespace std;

vector<pair<int, int>> v;
priority_queue<pair<int, int>> pq;

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

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int a, b;
        cin >> a >> b;

        pq.push(make_pair(b, a));
    }

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

    int answer = 0;
    while (L > P)
    {
        if (pq.empty())
        {
            cout << "-1";
            return 0;
        }

        pair<int, int> current = pq.top();
        pq.pop();

        if (current.second <= P)
        {
            answer++;
            P += current.first;

            for (int i = 0; i < v.size(); ++i)
            {
                pq.push(v[i]);
            }
            v.clear();
        }
        else
        {
            v.push_back(current);
        }
    }

    cout << answer;

    return 0;
}

 

✔ 정답 코드 2

• 가까운 순서로 주유소를 정렬한다. 
• 현재 P로 도달할 수 있는 주유소까지만 우선순위 큐에 넣는다. 
• 우선순위 큐의 top의 위치한 주유소를 방문한다. 
• 이를 반복

이렇게 하면 다시 처음부터 주유소를 탐색할 필요가 없어서 시간이 많이 절약된다. 

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

using namespace std;

vector<pair<int, int>> v;
priority_queue<int> pq;

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

    int N;
    int L, P;

    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int a, b;
        cin >> a >> b;

        v.push_back(make_pair(a, b));
    }

    cin >> L >> P;

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

    int answer = 0;
    int current_index = 0;
    while (L > P)
    {
        // 현재 연료로 도달할 수 있는 주유소들의 P를 우선순위 큐에 저장해 둔다.
        while (current_index < N && P >= v[current_index].first)
        {
            pq.push(v[current_index].second);
            current_index++;
        }

        // 현재 연료로 도달할 수 있는 주유소 중에서 가장 연료가 높은 주유소를 방문한다.
        if (!pq.empty())
        {
            P += pq.top();
            pq.pop();

            answer++;
        }
        else
        {
            // 만약 현재 연료로 도달할 수 있는 주유소가 없다면 -1 출력
            answer = -1;
            break;
        }
    }

    cout << answer;

    return 0;
}

•