[백준 13305번] [그리디] 주유소

잘 생각해보면, 주유할 수 있는 양이 무한대이므로 최소 가격으로 넣을 수 있을 때 최대한 많이 주유하는 것이 유리하다.

 

다만, 문제가 되는 지점이 현재까지의 최소 가격을 어느 상황까지 커버할 수 있는지가 미지수이다.

 

예를 들어 지역 1, 2, 3, 4를 방문하는 상황이라고 하자

지역 1에서 현재 기름을 3의 가격을 판매하고 있다고 하자.

 

일단 적어도 지역 2까지는 가야하므로 최소한 지역2까지 가는데 필요한 거리에 필요한 주유량은 구입해야 한다.

하지만, 그 이상의 거리까지 구매를 해야하는지 여부는 지역2의 기름 가격을 알아야 한다.

지역 2의 기름 가격보다 싸면, 지역 1에서 지역2에서 지역3까지 가는데 필요한 기름을 미리 구매하는 것이 더 유리하다.

 

즉, 지역 2에서 3으로 갈 때 사용되는 기름의 가격은 지역1과 2의 기름 가격 중 최소이다.

 

이를 반복 적용하면 지역 n에서 n+1으로 갈 때 사용되는 기름의 가격은 지역1~지역n까지의 기름 가격 중 최소이다.

즉, 쿼리의 최솟값을 지속적으로 구하는 상황과 동일하므로 우선순위큐를 통해 최솟값을 지속적으로 업데이트하면서 관리해주면 된다.

O(nlgn)에 충분히 처리 가능하다.

 

다만, 숫자가 상당히 큰 편이므로 long long 자료형을 써야한다는 점은 주의해야 한다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    int n;
    cin >> n;
    queue<ll> d;
    priority_queue<ll, vector<ll>, greater<ll> > pq;
    for(int i = 0; i < n - 1; i++){
        ll temp;
        cin >> temp;
        d.push(temp);
    }

    ll min_cost = 0;

    for(int i = 0; i < n; i++){
        ll temp;
        cin >> temp;
        if(i == n - 1) continue;
        pq.push(temp);
        
        ll cur_d = d.front(); d.pop();

        min_cost += cur_d * pq.top();
    }

    cout << min_cost << "\n";
    return 0;
}