[백준OJ] 13305번 주유소

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

13305번: 주유소

---

 

-풀이-

싼 가격의 도시를 만날때까지 현재까지 만나왔던 도시중 가장 싼 값의 기름을 이용하여 도로를 주행한다. 더 값싼 도시를 만난다면, 가장 싼 값의 기름을 갱신시켜준뒤, 도로를 주행하면된다.

 

-시간복잡도-

O(N)

 

-코드-

#include <iostream>
#include<algorithm>
using namespace std;

int road[1000001] = { 0 };
int n;
long long min_cost = 1000000001;
long long result = 0;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> road[i];
	}
	for (int i = 0; i < n; i++) {
		long long city;
		cin >> city;

		min_cost = min(min_cost, city);
		result += min_cost * road[i];
	}
	cout << result;
	return 0;
}