[C++] 백준 #13305번 주유소 17점/100점 문제 풀이 (Greedy Algorithm)

 

1. 문제 본문: 백준 13305번

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2 × 5 = 10원) 다음번 도시까지 이동한 후 3리터의 기름을 넣고(3 × 2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1 ×4 = 4원) 제일 오른쪽 도시로 이동하면, 총비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2 × 5 = 10원) 다음번 도시까지 이동한 후 4리터의 기름을 넣고(4 × 2 = 8원) 제일 오른쪽 도시까지 이동하면, 총비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

 

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1 이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

 

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다. 

 

 

2. 첫 번째 풀이 (17점)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);

    int N;//도시 개수
    cin >> N;

    long long length, price;//각각 도로 길이, 주유소 리터당 가격
    long long cost = 0; //최소 비용
    vector<long long> road;
    vector<long long> oil;

    for (int i = 0; i < N - 1; i++) {
        cin >> length;
        road.push_back(length);
    }

    int min = 1000000001, mIndex = 0;
    for (int i = 0; i < N - 1 ; i++) {
        cin >> price;
        oil.push_back(price);
        if (price < min) { //가장 저렴한 유가의 도시 찾기
            min = price;
            mIndex = i;
        }
    }
    cin >> price;//마지막 도시의 유가는 필요 없음
    

    for (int i = 0; i < N - 1; i++) {
        if (i < mIndex) {//최저 유가 도시 도착 전에는 다음 도시 가기 위한 기름만 구매
            cost += oil[i] * road[i];
        }
        else if (i == mIndex) {//최저 유가 도시에서 필요한 기름 다 사기
            int total = 0;
            while (i < N - 1) {
                total += road[i++];
            }
            cost += oil[mIndex] * total;
            break;
        }
    }
    
    cout << cost;

    return 0;
}

17점 코드는 min, mIndex라는 두 변수를 사용해서 문제를 풀었는데, 먼저 각 도시의 유가를 입력받으면서 최소 유가와 해당 도시의 인덱스를 저장해둔다. 그리고 for문을 돌면서 최소 유가 도시의 인덱스 전까지는 각 도시의 유가와 다음 도시까지 거리를 곱해 cost에 더하고, 최소 인덱스 이후부터는 해당 최소 유가에 남은 모든 거리를 더하는 로직으로 코드를 구성했다. 하지만 해당 코드는 17점밖에 받지 못한다. 왜일까? 반례는 아래와 같다.

 

{ 반례 }

5
2 3 1 1
5 2 4 1 1

답 : 19

 

위와 같이 입력하면 최소 인덱스는 3, 최소 비용은 1이다. 그럼 index=0,1,2에서는 각 도시 유가와 다음 도시까지의 거리를 곱한 값을 cost에 더해나갈 텐데, 위의 경우 index=1인 도시의 유가는 2원, index=2인 도시의 유가는 4원이다. 이런 경우 유가가 2원인 index=1 도시에서 index=3 도시까지의 거리 4km를 가기 위한 기름을 모두 충전하는 것이 index=2에서 3L, index=4에서 1L 주유하는 것보다 훨씬 이득이다. minimum 유가와 인덱스에만 집중하다 보니 중요한 포인트를 빼뜨린 것이다.

이를 보완한 풀이가 아래에서 이어진다.

 

 

 

3. 두 번째 풀이(100점)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);

    int N;//도시 개수
    cin >> N;

    long long length, price;//각각 도로 길이, 주유소 리터당 가격
    vector<long long> road;
    vector<long long> oil;


    //[1] 도로 길이 입력 받기
    for (int i = 0; i < N - 1; i++) {
        cin >> length;
        road.push_back(length);
    }

    //[2] 각 도시의 유가 입력 받기
    for (int i = 0; i < N ; i++) {
        cin >> price;
        oil.push_back(price);
    }
    
    long long min = oil[0];
    long long cost = road[0] * oil[0]; //최소 비용

    //[3] Greedy 알고리즘으로 최소 비용 찾기
    for (int i = 1; i < N - 1; i++) {
        if (oil[i] < min) {
            cost += oil[i] * road[i];
            min = oil[i];
        }
        else {
            cost += min * road[i];
        }
    }
    
    cout << cost;

    return 0;
}

17점 풀이와 다른 점은 [3] 번이다. 최소 유가를 구해야 하는 것은 이전 풀이와 동일하다. 하지만 입력받을 때 구하는 것이 아니라, cost를 구하는 과정에서 최소 유가와 현재 도시의 유가를 비교하면서 min값을 찾아내고, 현재 도시 유가가 더 저렴할 경우 현재 도시 유가를, min값이 더 저렴할 경우에는 min값을 다음 도시까지의 거리와 곱해서 cost에 더해나간다. 

또한 거리와 유가를 곱하는 과정에서 int를 넘어갈 수 있기 때문에 long long 타입으로 변수를 선언해야 한다.