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

 

먼저, 출발을 위해서 무조건 첫 주유소에서는 주유를 해야 한다.

지금까지 가장 저렴한 가격을 배열에 저장하는데, min_price[i-1]와 price[i]를 비교해서 더 저렴한 가격을 min_price[i]에 저장한다.

배열 min_price에 저장된 가격과 주유소 간의 거리 배열 len을 각각 곱하면 최솟값이 나온다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

long long len[100001] = { 0, }, price[100001] = { 0, }, min_price[100001];

int main() {
	int n;

	cin >> n;
	for (int i = 0; i < n - 1; i++) cin >> len[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]);
	}

	long long ans = 0;
	for (int i = 0; i < n - 1; i++) ans += len[i] * min_price[i];
	cout << ans;
}

 

찾아보니, 조금 더 이해하기 쉬운 코드가 있어 아래 추천한다.

[백준] 13305 주유소 (C++ - 그리디 알고리즘)