[백준] 13305 주유소 with C++

문제설명

---

입출력 예제

---

개념

　최소 비용을 통해 목표를 달성하는 그리드 알고리즘을 활용하는 문제다. 이 문제의 핵심 아이디어는 가장 낮은 기름값을 갖는 주유소를 찾아, 그곳에서 기름을 충전하는 것이다. 따라서 현재 위치에서 다음 도시로 이동하기 위해 필요한 기름을 충전하는데, 현재 주유소의 기름 가격과 다음 주유소의 기름 가격을 비교하여 최소 비용을 항상 유지하게 기름값을 갱신하면 된다.

---

풀이

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

int main()
{
	long long N;
	cin >> N;

	vector<long long> station(N), road(N-1);

	for (int i = 0; i < N - 1; ++i)
		cin >> road[i];

	for (int i = 0; i < N; ++i)
		cin >> station[i];

	long long minCost = station[0];
	long long ans = minCost * road[0];

	for (int i = 1; i < N - 1; i++)
	{
		minCost = min(minCost, station[i]);
		ans += minCost * road[i];
	}

	cout << ans;
}