[백준/c++] BOJ 13305 - 주유소

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

13305번: 주유소

 

문제 설명

N개의 도시가 있다. 각 도시에는 주유소가 있으며, 리터 당 가격은 다를 수 있다. 인접한 도시 사이의 도로들은 길이가 서로 다를 수 있으며 단위는 km이다. 1km 당 1리터의 기름을 사용한다. 제일 왼쪽에서 제일 오른쪽 도시로 이동할 때, 충전해야 하는 기름의 최소 비용을 구하라.

 

입력은 다음과 같은 순서로 들어온다.

도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)
인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수
주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수

거리는 1이상 1,000,000,000 이하의 자연수, 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

 

해결

기름 가격이 가장 작은 도시를 A라고 하자. 최소 비용으로 이동해야 하므로 A에서 기름을 최대한 많이 충전해야 한다. 또한 A에 도달하기까지 쓸 기름도 필요하므로, 도달하기 전까지 있는 도시 중에서 기름 가격이 가장 적은 곳에서 A까지 갈 수 있을 만큼 충전을 해야 한다. 이를 계속 적용해 나가면 현재 있는 도시보다 기름값이 적은 도시에 도착할 수 있을 만큼만 충전하면 된다는 것을 알 수 있다. 

물론 현재 기름이 이미 충분한 상태면은 충전을 하지 않고, 현재 있는 도시보다 기름값이 적은 도시가 앞에 없다면 제일 오른쪽 도시에 도착할 수 있을 만큼만 충전하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

long long dist[100001];
long long price[100001];
int main() {
	int n, idx = 0;
	long long answer = 0;
	cin >> n;
	for (int i = 0; i < n - 1; i++)
		cin >> dist[i];
	for (int j = 0; j < n; j++)
		cin >> price[j];

	while (idx != n - 1) {
		for (int i = idx + 1; i < n; i++) {
			if (price[idx] > price[i]) {
				for (int j = idx; j < i; j++)
					answer += price[idx] * dist[j];
				idx = i;
				break;
			}
			if (i == n - 1) {
				for (int j = idx; j < i; j++)
					answer += price[idx] * dist[j];
				idx = i;
			}
		}
	}

	cout << answer;
}