[백준/C++/Greedy] 13305 주유소

0. 문제

주유소 / 실3 / 13305 / greedy

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

 

주유소와 주유소 간 거리를 이동할 때 

이동에 필요한 기름을 주유해야 하는데

최소 주유 비용을 출력하는 문제이다

 

방법은 단순하다

경로를 따라 가다가 저렴한 지점에서 많이 주유해야

비싼 곳에서 주유하지 않아도 된다

 

1. 테스트 케이스 분석

 

백준에 있던 예제이다

 

인풋 첫 번째 줄에는 주유소 개수가 주어지고

두 번째 줄에는 주유소 간 거리가 주어지고

그 다음에는 각 주유소의 단위 리터 당 가격이 주어진다

 

주유소 개수가 n일 때 

주유소 간 거리는 n-1개의 값이 주어지고

주유소 별 가격은 n개의 값이 주어질 것이다

 

특정 주유소에 도달했을 때

그 지점 직전까지의 최소 가격을 저장해두었다가

두 값을 비교해서 더 저렴한 지점에서 주유하는 것으로 결정해야 한다

 

처음에는 출발해야만 하므로

처음 주유소에서는 무조건 주유해야하고

처음 주유소의 가격으로 최소 가격 변수를 초기화해야 한다

 

다음 주유소의 가격과 최소 가격 변수를 비교했을 때 

 

최소 가격이 더 저렴하다면 이번 지점에 주유해야할 양을

최소 가격인 주유소에서 더 주유하고 이번 지점에서는 주유를 하지 않는다

 

만약 최소 가격보다 더 저렴한 지점을 만났다면

최소 가격 변수를 갱신하고 이번 지점에서 다음 지점으로 갈 만큼 주유해야한다

 

2. 코드 구상

 

예제 설명할 때 대부분 다루었는데

 

핵심은 

처음에는 무조건 주유를 해야만 한다는 것과

 

이전 최솟값과 새로 만나는 주유소 가격을 비교해서

이전에 더 주유를 할지, 새로 만나는 곳에서 할 지 결정해야한다는 것

 

주유한 모든 주유소에서 주유한 가격을 모두 더해서

최종 가격을 출력해주어야 한다

 

3. 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;  // 도시 개수
    cin >> n;

    vector<int> distance(n - 1);  // 주유소 사이 거리
    vector<int> price(n);         // 각 주유소 가격

    // 거리 
    for (int i = 0; i < n - 1; i++) {
        cin >> distance[i];
    }

    // 주유소 가격
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }

    long long totalPrice = 0;    // total
    int minPrice = price[0];  // 최소 가격 

    // 주유소 순회
    for (int i = 0; i < n - 1; i++) {
        // 지금 주유소가 더 저렴할 때 min 업데이트
        if (price[i] < minPrice) {
            minPrice = price[i];
        }

        // 지금까지의 min으로 다른 도시 가는 주유 가격 계산
        totalPrice += (long long)minPrice * distance[i];
    }

    // 최종 total
    cout << totalPrice << endl;

    return 0;
}