1 문제

각 도시별 기름값과 도시 간 거리가 주어졌을 때 어디서 기름을 넣으면 가장 싸게 끝까지 도달할 수 있는지 계산

2 Idea

i번째 도시부터 출발해서 기름값이 더 싼 도시까지는 i번째 기름으로 간다.
문제에서 기름값이랑 도시간 거리가 10억까지기 때문에 long으로 계산하도록 구현한다.

3 Code

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

#include <iostream>
#include <vector>

long FindMinMoney(const std::vector<int>& d, const std::vector<int>& price, const int N){
    long answer = 0;

    for (int i=0; i<N;){
        int j;
        for (j=i+1; j<N; ++j){
            if (price[i]>price[j]){
                break;
            }
        }

        int d_sum = 0;
        for (int k=i; k<j; ++k){
            d_sum += d[k];
        }

        answer += static_cast<long>(d_sum)*static_cast<long>(price[i]);
        i=j;
    }

    return answer;
}

int main(){
    int N = 0;
    std::cin >> N;

    std::vector<int> d;
    std::vector<int> price;

    for (int i=0; i<N-1; ++i){
        int _d = 0;
        std::cin >> _d;

        d.push_back(_d);
    }

    for (int i=0; i<N; ++i){
        int _price = 0;
        std::cin >> _price;

        price.push_back(_price);
    }

    std::cout << FindMinMoney(d, price, N) << std::endl;

    return 0;
}