[Baekjoon,13305] 주유소

현재 위치의 리터당 가격보다 낮은 도시가 나올 때까지 충전하여 이동한다. 더 낮은 가격의 도시가 나온다면 이곳에서 이곳보다 더 낮은 가격의 도시가 나올 때까지 이동한다. 이를 반복하여 마지막 도시에 도착하면 종료한다. 아래의 그림을 보면 이해할 수 있다. 비용이 5인 도시에서 출발하여 더 낮은 비용 2를 가진 도시에서 다시 충전하여 이동하는 것을 볼 수 있다.

이를 코드로 구현하면 아래와 같다. 이때 1,000,000,000의 크기를 가진 거리와 가격 때문에 int형을 이용하면 오버플로우가 발생한다. 따라서 long long 형을 이용해야 한다.

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

const int MAX = 100001;

int N;
int dist[MAX], price[MAX];

long long solve()
{
	long long totalCost = 0;
	int minPrice = price[0];
	for (int i = 0;i < N-1;++i)
	{
		// 더 값싼 비용이 나오면 이를 이용
		minPrice = min(minPrice, price[i]);
		totalCost += (long long)minPrice*dist[i];
	}
	return totalCost;
}

int main()
{
	cin >> N;
	for (int i = 0;i < N - 1;++i)
		scanf("%d", &dist[i]);
	for (int i = 0;i < N;++i)
		scanf("%d", &price[i]);

	cout << solve() << endl;
	return 0;
}