백준 13305 주유소 / C++

문제 : 13305

풀이 point

가장 기름값이 싼 주유소에서 나머지 킬로 수를 다 커버하는 것이 이득이다.
기름 값이 싸지 않은 주유소에서는 다음 주유소로 가기 위한 기름만 채운다.

풀이 방법

위의 발상을 코드로 구현한다. min값과 기름 값을 비교해나가며 min값보다 작으면 가장 싼 주유소의 기름 값을 교체해주고, 계속해서 길x기름값을 해준다.
만약 min값보다 작은 것이 또 나왔다면 계속 교체해주고, 나오지 않았다면 가장 싼 주유소에서 계속해서 기름을 넣는 형식이다.

주의할 점 : 100점을 맞기 위해서는 고려해야할 것이 있다. 바로 범위가 int 범위를 넘을 수 있다는 것. long long으로 바꾸어주면 해결된다.

코드

//백준 13305, 주유소

#include <iostream>
#include <climits>

int main (){

    long long N;
    long long len[100'000];
    long long price[100'001];
    std::cin >> N;
    
    for(auto i{0}; i<N-1; ++i){
        std::cin >> len[i];
    }

    for(auto i{0}; i<N; ++i){
        std::cin >> price[i];
    }

    //본인보다 작은 값이 나올때까지 주유*거리
    long long min{LONG_MAX}; long long minIdx{0}; long long sum{0}; 
    for(auto i{0}; i<N-1; ++i){
        if(price[i] < min){
            min = price[i];
            minIdx = i;
            sum += price[i] * len[i];
        }
        else{
            sum += price[minIdx] * len[i];
        }
    }

    std::cout << sum;

    return 0;
}