문제
풀이
지나치는 주유소 마다 기존의 최솟값보다 크다면, 최솟값으로 다음 도시로 이동하는 만큼 주유를 하고, 최솟값보다 작으면 그 값으로 최솟값을 갱신하여 다음 도시로 이동하는 식으로 최솟값을 찾아냈다. 물론 현실적으로 도시를 지나쳤음에도 불구하고 최솟값 도시의 주유소에서 주유를 할 수 있다는 것이 말이 안되긴하다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N;
scanf("%d", &N);
vector<long long> distance;
long long distance_sum = 0;
for(int i = 0; i<N-1; i++){
long long input1;
scanf("%lld", &input1);
distance.push_back(input1);
distance_sum = distance_sum + input1;
}
vector<long long> cost;
for(int i = 0; i<N; i++){
long long input2;
scanf("%lld", &input2);
if(i == N-1){
break;
}
else cost.push_back(input2);
}
long long sum = 0;
long long cost_current = 1000000001;
for(int i = 0; i<N-1; i++){
if(cost[i] < cost_current){
cost_current = cost[i];
sum = sum + cost_current * distance[i];
}
else{
sum = sum + cost_current * distance[i];
}
}
printf("%lld\n", sum);
}
