[BOJ] C++ 13305: 주유소 - 우선순위 큐와 그리디 알고리즘

13305번: 주유소

예제

4
2 3 1
5 2 4 1

ans : 18

4
3 3 4
1 1 1 1

ans : 10

---

문제를 잘 생각해 보면 기름 값이 가장 싼 도시를 3번 도시라고 하자. 그럼 3번 도시부터 목적지까지의 거리만큼 기름을 3번 도시에서 다 사두고 2번 도시를 다시 목적지로 두고 반복하면 된다.

 

이렇게 구현한다면 기름 값이 가장 싼 도시를 계속해서 갱신해야 하므로 우선순위 큐를 사용했다. 그리고 목적지를 갱신하는 방법은 좀 번거로워서 방문처리를 하는 방식을 채택했다. 어차피 시간이 2초라 이런 사소한 부분은 시간초과에 영향을 줄 것 같지 않았다.

 

시간 복잡도를 계산해보면 도시는 100,000개가 있고 우선순위 큐의 push, pop에는 log n의 시간이 든다. 최대 n번 반복하므로 n log n이고 2초 안에 해결이 가능하다 생각해서 바로 구현했다. 다만 주의할 점이 있는데 답을 구하는 과정에서 기름값과 거리를 곱해야 한다. 기름값과 거리의 최대값이 100,000,000이므로 int 자료형의 최대값은 가뿐히 넘어가서 long long으로 구현해 줬다. long long을 쓴다면 괜히 복잡하게 어떤 건 int로 구현하고 그렇게 하지 말고 무식하게 모두 long long으로 하는 게 문제풀이에서는 안전하다.

/** 그리디 13305 주유소 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
long long n, ans = 0;
long long dist[100100];
bool visited[100100];
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> cost;

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

    cin >> n;
    for (long long i = 0; i < n - 1; i++)
        cin >> dist[i];
    for (long long i = 0; i < n; i++)
    {
        long long cost_;
        cin >> cost_;
        cost.push({cost_, i});
    }
    // dist[i] : i -> i+1 거리
    // cost[i] : i번 도시의 기름값

    while (!cost.empty())
    {
        auto min = cost.top();
        cost.pop();
        // min_idx에서 살 수 있는만큼 다 사기
        for (long long i = min.second; i < n - 1; i++)
        {
            if (visited[i])
                break;
            ans += min.first * dist[i];
            visited[i] = true;
        }
    }

    cout << ans << '\n';
}