BOJ (C/C++) 13305번: 주유소

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

13305번: 주유소

---

풀이

출발할 때는 처음 도시의 기름 가격으로 처음 도로의 길이만큼 가야 하므로 초기값은 Road[0] * Oil[0]로 설정.두 번째 도시에 도착한 이후로는 i번째 도시의 기름 가격이 i-1번째 도시보다 크다면 i-1번째 도시에서 i+1번째 도시에 도달할 수 있을 만큼 주유하면 되므로 해당 로직을 반복하여 제일 오른쪽 도시까지 이동.(제일 오른쪽 도시의 값은 무시 가능)

---

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector <unsigned long long int> Road, Oil;
int main() {
	unsigned long long int N, r, o;
	scanf("%llu", &N);

	// input
	for (int i = 0; i < N - 1; i++) {
		scanf("%llu", &r);
		Road.push_back(r);
	}

	for (int i = 0; i < N; i++) {
		scanf("%llu", &o);
		Oil.push_back(o);
	}

	unsigned long long int money = Road[0] * Oil[0];
	o = Oil[0];
	for (int i = 1; i < N - 1; i++) {
		if (o > Oil[i]) o = Oil[i]; 	// 다음에 도시의 기름 가격이 더 싸다면 오일 가격 변경
		money += o * Road[i];
	}

	printf("%llu", money);
	return 0;
}