백준 주유소 13305 C++

가장 오른쪽 도시까지 가는데 드는 최소 비용을 구하는 문제.

현재 시점에서 최소 비용을 비교하면 쉽게 풀 수 있다.

기름을 한 번에 넣어간다는 생각으로 접근하면 쉽지 않다.

대신 기름이 더 싼 경우 최저가격을 갱신하고, 그렇지 않으면 기존 가격을 유지한다고 생각하면 쉽다.

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

long n, price;
vector<long> road;
vector<long> gas;

int main() {
	cin >> n;

	long a;
	for (int i = 0; i < n - 1; i++) {
		cin >> a;
		road.push_back(a);
	}

	for (int i = 0; i < n - 1; i++) {
		cin >> a;
		gas.push_back(a);
	}
	
	price += gas[0] * road[0]; //출발 할 때 기름
	int idx = 0;
	for (int i = 1; i < n-1; i++) 
		if (gas[i] < gas[idx]) { //다음 마을의 기름이 더 싼 경우
			idx = i;
        price += gas[idx] * road[i];
	}
	cout << price;
 }

주의할 점으로는 입력값이 크기 때문에 int가 아닌 long을 사용해야한다.