[백준] 13305 : 주유소

https://www.acmicpc.net/problem/13305

13305번: 주유소

---

• 도시와 각 기름값이 일렬로 주어져 있고, 차는 반드시 그 방향만으로 지나가야 한다.
• 전체 기름값을 최소로 하려면, 각 도시들마다 현재까지 지나온 주유소들 중에 기름값이 가장 싼 주유소에서 기름을 산다고 생각하면 된다.
• 그 다음으로 기름값이 더 싼 주유소가 나오기 전까지는 현재의 최소값으로 도시들을 지나오고, 더 싼 주유소가 나오면 그 다음 더 싼 주유소가 나올때까지 그 값으로 도시들을 지난다.

---

#include <iostream>

using namespace std;

int N, w;
unsigned long long answer = 0;              // 오버플로우 대비 ull
unsigned long long min_price = 1000000000;
int length[100001];

int main(void)
{
    cin >> N;
    for(int i = 1 ; i <= N-1 ; i++)         // 도시 간의 거리를 일단 배열에 저장
    {
        cin >> w;
        length[i] = w;
    }
    for(int i = 1 ; i <= N ; i++)           // 각 지점의 기름 값을 확인하면서
    {
        cin >> w;
        if(w < min_price) min_price = w;    // 현재위치까지의 기름의 최솟값을 저장
        answer += (min_price * length[i]);  // 다음 최소값이 나올때까지 현재 최소값의 기름으로 도시를 경유
    }

    cout << answer << endl;
}