백준 13305 주유소

˙www.acmicpc.net/problem/13305

13305번: 주유소

그리디하게 접근하면 쉽게 풀리는 문제다.

 

내 접근법은 이렇다.

 

1. 현재 지역이 다음 지역보다 가격이 비싸다면 그 다음 지역을 검색해서 현재 지역보다 싼 지역을 찾음

2. 현재 지역보다 싼 지역을 찾았다면 그 지역까지의 거리값만큼 충전 후 이동

3. 이후 반복

 

 

단, 첫 번째 지역에서 반드시 충전해야 한다.

#include <iostream>
using namespace std;
using ll = long long;

ll ar[100001], dist[100000];

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

	ll n, ans = 0;
	cin >> n;
	for (int i = 0; i < n - 1; i++) cin >> dist[i];
	for (int i = 0; i < n; i++) cin >> ar[i];

	int i = 0, j = 1;
	while (1) {
		if (i == n) break;

		while (ar[i] < ar[j]) j++;
		if (j - i > 1) { //거리의 차가 1이 넘는다면
			ll sum = 0;
			for (int v = i; v < j; v++) {
				sum += dist[v]; //이동해온 거리의 합을 더해주고
			}
			ans += ar[i] * sum; //현재 가격*거리의 합
		}
		else {
			ans += ar[i] * dist[i];
		}
		i = j++;
	}
	cout << ans << endl;

	return 0;
}

계산의 합이 int 형 범위를 초과하는것을 조심해야 한다.