출발할 때는 처음 도시의 기름 가격으로 처음 도로의 길이만큼 가야 하므로 초기값은 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;
}
