문제 풀이
문제를 해결하는 방법은 심플하다.
최대한 싼 곳에서 기름을 많이 넣자.
그럼, 모든 곳마다 얼마큼 넣어야하는지를 탐색하면서 구해야할까?
아니다. 그냥 앞에서부터 뒤에까지 탐색을 하면서, 그 지점까지 오면서 싼 가격이 얼마였는지 기록해놓고 그때그때 가야 하는 거리에 해당 가격을 곱해서 누적해가면 된다.
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define for1(s,n) for(int i = s; i<n; i++)
using namespace std;
typedef long long ll;
ll N, ans, mn;
ll dis[110000];
ll cost[110000];
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> N;
for1(1, N) cin >> dis[i];
for1(0, N) cin >> cost[i];
mn = cost[0];
for1(1, N) {
ans += dis[i] * mn;
mn = min(mn, cost[i]);
}
cout << ans;
}
끝