[백준 13305번] 주유소

문제 링크: 

<문제 풀이> 그리디 알고리즘

 

현재까지 발견한 가격들 중 최소의 주유 가격으로 다음 최소 주유 가격을 발견할 때까지 이동하는 것을 반복하면 그것이 최적의 해가 됩니다.

 

위 그림에서

 

최솟값 5에서 다음 최솟값을 갱신할 때까지 이동하면 다음 위치는 2

최솟값 2에서 다음 최솟값을 갱신할 때까지 이동하면 다음 위치는 1

 

구현할 때는 바로 다음 위치까지 이동하는 것이 아닌 도시를 하나씩 방문하면 됩니다.

방문할 때마다 현재까지 발견한 가격들 중 최소의 주유 가격을 임시 변수에 저장하고 있어야 합니다.

현재 도시에서 다음 도시로 이동할 때 드는 비용은 (최솟값*거리)가 됩니다.

 

<C++소스코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long ll;
 
int n;
ll price[100000];
ll dist[100000];
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> dist[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }
 
    ll ans = price[0] * dist[0]; //처음에는 기름을 모두 넣고 다음 도시까지 간다.
    ll cur = price[0]; //현재까지 방문한 도시들의 주유 가격 중 최솟값
    for (int i = 1; i < n - 1; i++) {
        if (price[i] >= cur) { // 더 작은 주유 값을 발견하지 못하면
            ans += dist[i] * cur; // 현재까지 방문한 주유 최솟값으로 다음 도시로 이동
        }
        else { // 더 작은 주유 값을 발견하면
            cur = price[i]; // 최솟값 갱신
            ans += dist[i] * cur; // 최소 주유 값으로 다음 위치까지 이동
        }
    }
    cout << ans;
    return 0;
}