cpp) 백준 13305: 주유소

Problem

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

13305번: 주유소

 

 

Solution

#include<iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    long long dist[100001];   // 도로의 길이
    long long price[100001];  // 주유소 기름 가격

    int n;            		// 도시의 개수
    long long total;        // 총 비용 = 정답값
    long long min_price;    // 최소 비용
    cin >> n;

    // dist 입력 받기
    for(int i=0;i<n-1;i++){
        cin >> dist[i];
    }

    // price 입력 받기
    for(int i=0;i<n;i++){
        cin >> price[i];
    }

    total += dist[0] * price[0];   // 필수 요건
    min_price = price[0];          // 최솟값 초기화

    for(int i=1;i<n-1;i++){
        if (min_price>price[i]){
            min_price = price[i];
            total += min_price * dist[i];
        } else {
            total += min_price * dist[i];
        }
    }

    cout << total << '\n';

   return 0;
}

 

 

Reference

https://wooono.tistory.com/431

[Greedy] 백준 13305번 "주유소" C++ 풀이