(13305) 주유소

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

단계별로 풀어보기

23단계(그리디 알고리즘) 5번째

 

 

 

i번째 도시에서 i+1번째 도시로 가는 비용을 최소화하는 방법은 1~i번 도시 중 가장 기름값이 싼 도시에서 거리만큼 기름을 채워오는 것이다. 따라서 1번 도시부터 N-1번 도시까지 순차적으로 돌며 최저 기름값과 비교하여 갱신하면 된다.

기름값이 갱신된 것은 이번 도시에서 기름을 채웠다는 의미고, 갱신되지 않았다면 이전 도시에서 기름을 (다음 도시까지만 갈 양보다) 더 많이 채웠다는 의미다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<long> v(n-1), w(n);
  
  for(int i=0;i<n-1;i++)  cin >> v[i];
  for(int i=0;i<n;i++)  cin >> w[i];
  
  long cost= w[0], ans= 0;
  
  for(int i=1;i<n;i++){
    ans+= cost*v[i-1];
    cost= min(cost, w[i]);
  }
  
  cout << ans;
  
  return 0;
}