[그리디 #7] BOJ 13305 - 주유소

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

13305번: 주유소

 

접근 방법

예제 1을 살펴보자.

 

여기서 중요한 점을 체크해봤다.

 

1. 첫번째 도시에선 무조건 기름을 구입해야한다.

2. 마지막 도시의 기름값은 무시한다.

3. 현재 도시에서 다음 도시들 중 현재 도시의 기름값보다 싼 도시까지 가는 기름만 구매한다.

(2에서 4를 거쳐 1로 가는 과정에서 2보다 싼 도시까지가는 거리의 기름을 산다.)

 

예를 들어 2 4 5 1 3 이런 도시가 있다고할 때,

2에서 1까지 가는 거리만큼 기름을 사야한다.

 

코드

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

using namespace std;
#define MAX 100001

int n;
long long price[MAX];
long long distances[MAX];
long long totalPrice;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

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

	for (int i = 0; i < n; i++)
		cin >> price[i];


	int idx = 0;
	while (idx < n-1) {
		long long currPrice = price[idx];
		long long totalDis = distances[idx];
		
		int i = idx + 1;
		//cout << "currPrice: " << currPrice << " , price[i]: " << price[i] << endl;
		for (; currPrice <= price[i]; i++) {
			//cout << "currPrice: " << currPrice << " , price[i]: " << price[i] << endl;
			totalDis += distances[i];
		}

		totalPrice += (totalDis * currPrice);
		//cout << "totalPrice: " << totalPrice << endl << endl;
		idx = i;
	}

	cout << totalPrice;

}