[BOJ] 12205 주유소

문제 풀이

12205번: 주유소

문제를 해결하는 방법은 심플하다.

최대한 싼 곳에서 기름을 많이 넣자.

그럼, 모든 곳마다 얼마큼 넣어야하는지를 탐색하면서 구해야할까?

아니다. 그냥 앞에서부터 뒤에까지 탐색을 하면서, 그 지점까지 오면서 싼 가격이 얼마였는지 기록해놓고 그때그때 가야 하는 거리에 해당 가격을 곱해서 누적해가면 된다.

풀이 코드

#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;
}

끝