주유소 (feat. 백준, 13305번)

주유소
https://www.acmicpc.net/problem/13305

13305번: 주유소

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
long long dist[100000], cost[100000];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register long long ans = 0, tmp;
	register int N;
	cin >> N;
	for (register int n = 0; n < N - 1; ++n)
		cin >> dist[n];
	for (register int n = 0; n < N; ++n)
		cin >> cost[n];
	tmp = cost[0];
	ans = tmp * dist[0];
	for (register int n = 1; n < N; ++n) {
		if (tmp < cost[n])
			ans += dist[n] * tmp;
		else
			tmp = cost[n], ans += dist[n] * tmp;
	}
	cout << ans;
	return 0;
}
// *&)*@*

문제에서 주어진 아래 그림을 예로 보겠습니다.

1. 동그라미 5, 2, 4, 1는 리터당 가격입니다. 각각을 C1, C2, C3, C4 라고 해보겠습니다. 
2. 직선 2, 3, 1은 거리 입니다. 각각을 D1, D2, D3 이라고 해보겠습니다.
3. D1만큼 가기 위해서는 무조건 C1에서 주유해야 합니다. 따라서 tmp라는 변수에 C1을 넣어보겠습니다. 최초의 주유 가격은 2 * 5 = 10 입니다. 정답이 10보다 작을 수는 없습니다.
4. C1은 C2보다 큽니다. 따라서 D2는 C2에서 주유하는게 더 이득입니다. 따라서 tmp라는 변수에 C2를 넣어보겠습니다. 그리고 누적 주유 가격 10에 2 * 3 을 더하여 16이 됩니다.
5. C2는 C3보다 작습니다. 따라서 D3는 C2에서 주유했어야 더 이득입니다. 따라서 tmp라는 변수를 갱신하지 않습니다. 따라서 16 + tmp * D2 = 16 + (2 * 1) = 18 입니다.
6. 이를 점화식으로 만들면 다음과 같습니다.

tmp = C1; total_cost = D1 * tmp; if Cn-1 < Cn    total_cost += Dn * tmp; else    tmp = Cn;    total_cost += Dn * tmp;