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

오늘은 백준13305번 주유소 문제를 풀어보도록 하자. 난이도에 비해 정답률이 꽤 낮았다. 우선 위 문제는 자료형이 중요하다. 문제를 보면 알겠지만 거리와 리터 당 가격은 10억 가까이 된다.

입력받는 배열은 int타입도 상관없지만(21억 under) 저장변수들은 21억을 훌쩍 넘길 수 있기에 int형이 아닌 long long 타입을 선언해야한다.

위를 유념하고 접근해보자.

문제는 다음과 같다.

                               [접근법]

  1. 맨 왼쪽 도시에서 오른쪽 도시로 가는데 최소의 비용으로 가야한다. 따라서 city배열을 처음부터 탐색하면서 기름 값이 작은 곳을 찾는다.
  
  2. 만일 찾지 못할 경우 distance에 거리를 계속 누적합을 해준다. 찾을 경우엔 원래 기름 값 * distance을 result에 누적합 후 distance = 0, price는 찾은 기름으로 갱신해준다.

  3. 마지막이 중요한데, 아직 계산이 끝난 것이 아니다. 도달하기 전 까지의 계산만 해준 것이므로 출력 값에  price * (distance + meter[n - 1])를 더해주어야 한다.

                                     [코드]
#include <iostream>
#include <algorithm>
using namespace std;

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

	int meter[100001];
	int city[100001];
	int n;
	long long result = 0, price = 0, distance = 0;

	cin >> n;

	for (int i = 1; i < n; i++) {
		cin >> meter[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> city[i];
	}

	price = city[0];

	for (int i = 1; i < n - 1; i++) {
		if (price > city[i]) {
			result += price * (distance + meter[i]);
			price = city[i];
			distance = 0;
		}
		else {
			distance += meter[i];
		}
	}
	cout << result + price * (distance + meter[n - 1]) << '\n';
}