[백준/C++] 13305번: 주유소(S4)

문제

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

13305번: 주유소

 

 

사용한 알고리즘

2022.01.22 - [PS/Algorithm] - [알고리즘 개념정리] 4. 그리디

 

 

풀이 

리터 당 가격이 가장 싼 주유소가 있는 도시에서 최대한 많은 기름을 넣는 게 이득이다.
따라서  임의의 (i-1)번 도시에서 i번 도시로 가는 기름은 
1~(i-1)번 도시의 주유소들 중 가장 리터당 가격이 싼 주유소에서 넣고 오는 게 최적 전략이다.

1. road[n-1]와 price[n] 배열에 각각 도로의 길이, 리터당 가격을 입력받는다.
2. 도로의 길이를 순회하며, 현재보다 왼쪽에 있는 주유소들 중 가장 저렴한 가격 * 도로의 길이를 ans변수에 더해준다.
3. ans를 출력한다.

 

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll n,ans=0; cin>>n;
    ll road[n], price[n];
    // 1. road[n-1]와 price[n] 배열에 각각 도로의 길이, 리터당 가격을 입력받는다.
    for(int i=0; i<n-1; i++) cin>>road[i];
    for(int i=0; i<n; i++) cin>>price[i];

    // 2. 도로의 길이를 순회하며,
    //    현재보다 왼쪽에 있는 주유소들 중 가장 저렴한 가격 * 도로의 길이를 ans변수에 더해준다.
    ll Pmin=price[0];
    for(int i=0; i<n-1; i++){
        Pmin=min(Pmin,price[i]);
        ans+=road[i]*Pmin;
    }
    // 3. ans를 출력한다.
    cout<<ans;
    return 0;
}