백준 13305번 문제 바로가기

문제에 대한 첫 인상

보통 문제에 최소 비용 이라는 표현이 들어가면 greedy 알고리즘으로 풀어내는 경우가 많은 것 같다. 이 문제도 각 주유소에서 비용을 최소로 한 것이 전체 비용도 최소가 되도록 한다.

나의 풀이

솔직히 마지막 주유소의 price는 필요 없는 정보였다. 앞에서부터 차례대로 주유소를 지나오면서 이전까지의 기름의 최솟값보다 더 저렴하면 prev에 새로운 기름값을 저장하고, 비용을 구해나가면 된다. 시간-비용 그래프를 그려보면 점차 하강하는 계단식의 그래프 형태를 띈다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N; // 주유소 갯수
    vector<long long> distance; // 주유소 사이 거리
    vector<long long> price; // 주유소별 리터당 가격
    long long cost = 0; // 총 비용
    long long prev = 1000000000; // 전 주유소 비용
    long long temp;
    
    cin >> N;
    for (int i=0; i<N-1; i++){
        cin >> temp;
        distance.push_back(temp);
    }
    for (int i=0; i<N; i++){
        cin >> temp;
        price.push_back(temp);
    }
    
    for (int i=0; i<N-1; i++){
        prev = min(prev, price[i]);
        cost += prev*distance[i];
    }
    
    cout << cost;
    return 0;
}