백준 13305번 주유소 - C++ 풀이

---

 

1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다.

 

1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다.

 기름통의 크기가 무제한이므로, 그리디하게 각 도시에 도착하기 전에 가장 싼 주유소에서 기름을 넣고 오면 최적이다. 일반화하면, i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 주유소에서 넣고 오면 된다. 이때 i-1번 도시에서 i번 도시까지의 거리를 dist[i], 1~(i-1)번 도시 중 가장 싼 주유소의 가격을 min_price[i]라고 하면 비용은 dist[i] * min_price[i]이다.

 

반응형

---

#include <iostream>

using namespace std;
typedef long long ll;

int N;
ll dist[100001], price[100001], min_price[100001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N-1; i++) cin >> dist[i];
    for (int i=0; i<N; i++) cin >> price[i];
    
    min_price[0] = price[0];
    for (int i=1; i<N; i++) {
        min_price[i] = min(price[i], min_price[i-1]);
    }
    
    // 가장 싼 곳에서 넣고 온다
    ll ans = 0;
    for (int i=0; i<N-1; i++) ans += dist[i] * min_price[i];
    cout << ans;

    return 0;
}