< 백준 BaekJoon : 13305번 주유소 > C++

<< 문제 >>

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

 

<< 풀이 >>

 

단순하게 생각해보면 더 가격이 싼 주유소가 나올때까지 필요한 기름만 구매하면 된다. 

 

Greedy 알고리즘을 통해 그때그때 파악해주면 된다. 

 

 

<< 코드 >>

#include <iostream>
#include <vector>
using namespace std;
 
 
long long lw[100001];
long long op[100001];

int main()
{
    int n
    cin >> n;
    
    for( int i=0; i<n-1; i++){
        cin >>lw[i];
    }
    
    for( int i=0; i<n; i++){
        cin >>op[i];
    }
    
    long long totalPrice = 0;
    int oil = lw[0]; // 구매 양, 다음 지점 까지는 무조건 사야하니
    long long nowPrice = op[0];
    
    for(int i=1; i<n; i++)
    {
        if(nowPrice > op[i])
        {
            totalPrice += oil * nowPrice;
            oil = lw[i];
            nowPrice = op[i];
        }
        else
        {
            oil += lw[i];
        }
    }
    
    totalPrice += oil * nowPrice; // 마지막까지 남아있는 경우 
    
    cout << totalPrice;
    
    return 0;
}

 

 

<< 깃헙 >> 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/13305.%E2%80%85%EC%A3%BC%EC%9C%A0%EC%86%8C

StudyAlgorithm_Part2/백준/Silver/13305. 주유소 at main · J2on/StudyAlgorithm_Part2