[Algorithm] 백준 - 주유소 (13305번)

문제

[백준] 주유소
(Olympiad > 한국정보올림피아드 > KOI 2016 > 중등부 2번)

사용 알고리즘

- 그리디 (Greedy)

해결방법

• 마을이 일직선 상에 있다는 것이 포인트
• 한 마을에서 다음 마을로 이동하기 전에 가장 저렴한 주유소를 저장해 두고 해당 주유소에서 주유한 뒤 이동한다
• 매 번 마을에 도착할 때마다 최소 주유비에 다음 이동 거리를 곱해서 경비를 구해야한다

예제 1

• 예제 1의 경우 각 마을의 주유비가 [5, 2, 4, 1] 이다. 이 때 이동할 때마다 그리디 하게 주유비를 선택한다고 하면 다음과 같다.

i	현재 주유비	최소 주유비	이동 거리	경비
0	5	5	2	10
1	2	2	3	6
2	4	2	1	2

소스코드

사용언어 : C++

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

int N; // 도시 개수
ll dist[100002]; // 거리
ll cost[100002]; // 비용

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;

    for (int i=0; i<N-1; i++) {
        cin >> dist[i];
    }
    for (int i=0; i<N; i++) {
        cin >> cost[i];
    }

    ll result = 0;
    ll min_cost = cost[0]; // 주유 최소 비용

    for (int i=0; i<N-1; i++){
        if (min_cost >= cost[i]) { // 도착한 마을의 주유 비용이 더 저렴한 경우
            min_cost = cost[i];
        }

        result += min_cost * dist[i];
    }

    cout << result;

    return 0;
}

 

한줄평

매 순간마다 최선의 선택을 해야한다는 점을 다시 한 번 생각해본다