[BOJ/C++] 13305 주유소

문제

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

풀이

⚠️자료형 long long

전형적인 Greedy 문제 + 코테 빈출

각 도시에 도착하기 전에 가장 싼 주유소에서 기름을 넣고 오면 최적
(i-1)번 도시에서 i번 도시로 이동하기 위한 기름을 1~(i-1)번 도시 중 가장 싼 주유소에서 넣고 오면 됨

(i-1)번 도시에서 i번 도시까지의 거리 : dist[i]
1~(i-1)번 도시 중 가장 싼 주유소의 가격 : min_price[i]
➡️비용 : dist[i] * min_price[i]

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;
	vector<long long> dist(N-1);
	vector<long long> price(N);
	vector<long long> min_price(N);
	long long ans = 0;

	for (int i = 0; i < N - 1; i++) {
		cin >> dist[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> price[i];
	}

	min_price[0] = price[0];
	for (int i = 1; i < N; i++) {
		min_price[i] = min(min_price[i - 1], price[i]);
	}

	for (int i = 0; i < N - 1; i++) {
		ans += dist[i] * min_price[i];
	}

	cout << ans;

	return 0;
}