[백준] 13305번 : 주유소

문제

 

---

풀이

 

말도 안되는 상상이지만 이런 생각을 해보자. 모든 도시의 주유소에 차와 연결할 수 있는 아주 긴 호스가 있다고 말이다.

다만 특정 주유소와 호스를 연결하려면 그 주유소까지 가야할 것이다. 그럼 저 자동차의 이동과정을 살펴보자.

 

일단 출발하기 전 주유를 해야한다. 다음 주유소까지 2km이니 2km 만큼의 기름을 첫번째 주유소에서 주유한다. => 5x2 = 10

두번째 주유소에 도착했다. 지난 주유소보다 가격이 저렴해 여기서 충전하기로 한다. 보라색 호스를 연결하고 3km 만큼의 기름을 주유한다. => 2x3 = 6

세번째 주유소에 도착했다. 연결된 호스의 주유소보다 가격이 비싸 이전 주유소에서 호스를 통해 기름을 받아오기로 했다. => 2x1 = 2

네번째 주유소에 도착했다. 도착지에 왔으니 기름을 충전할 이유는 없다.

 

이 결과를 전부 더하면 10+6+2 = 18 최솟값이 나온다. 이 과정을 코드로 작성하자.

---

소스코드

 

#include <iostream>

using namespace std;

struct city_info {
    long long dist;
    long long oil;
};

long long min_oil(city_info *c, int length) {
    long long cur_oil = c[0].oil;
    long long money = 0;

    for (int i = 0; i < length; i++) {
        if (c[i].oil < cur_oil) //이번 도시의 기름 가격이 지금 넣고 있던 기름 가격보다 저렴하면 기름 변경
            cur_oil = c[i].oil;
        money += (cur_oil * c[i].dist);
    }
    return money;
}

int main() {
    int N;

    cin >> N;
    city_info *city = new city_info[N];

    for (int i = 0; i < N - 1; i++)
        cin >> city[i].dist;
    city[N - 1].dist = 0;
    for (int i = 0; i < N; i++)
        cin >> city[i].oil;

    cout << min_oil(city, N);
}

현재 사용하는 주유소의 기름값을 cur_oil 변수에 저장한다. 초깃값은 첫번째 주유소의 기름값일 것이다.

다음 도시에 도착할 때마다 기름값을 비교하고 새로운 주유소의 기름값이 더 저렴하다면 cur_oil 변수를 그 값으로 변경한다.