(백준/C++) 13305_주유소

주유소 문제는 탐욕 알고리즘으로 풀 수 있는 문제입니다.

탐욕 알고리즘(Greedy Algorithm)이란, 매 순간 최적이라고 생각되는 방법을 선택하는 방식으로 문제를 해결하는 알고리즘입니다.

즉, 다른 경우의 수를 생각하지 않고 현 문제에서 가장 좋아 보이는 것을 선택하다 보면 문제가 풀리는 알고리즘 입니다.

13305번: 주유소 (acmicpc.net) 문제는 문제가 길어서 자칫 복잡해 보이지만, 생각보다 쉬운 문제입니다.

도로를 이용할 수 있는 만큼 기름을 충전해야 하는데, 가장 가성비 좋게 주유하는 방법을 물어보는 문제입니다.

물론, 도시마다 가격이 다르고 현재 도시에서 목적지까지의 도로 길이가 다 다르기 때문에 복잡하게 생각하는 순간 헤맬 수 있는 문제입니다.

---

접근법

이 문제의 핵심은 현재 도시의 기름 가격이 다음 도시보다 싸다고 해도, 현재 도시에서 가능한 한 많은 기름을 넣는 것이 아니라, 다음 도시까지 가는 데 필요한 만큼만 기름을 넣는 것입니다.

그리고 다음 도시로 이동하면서 그 도시의 기름 가격과 그 다음 도시의 기름 가격을 비교하고, 이 과정을 반복하면 됩니다.

1) 처음 도시에서 시작

제일 왼쪽 도시에서 출발하므로, 먼저 그 도시의 주유소에서 기름을 넣습니다.

이때, 다음 도시의 기름 값으로 뭔가 복잡한 계산을 하려고 하지 말고, 다음 도시까지의 거리만큼 기름을 넣습니다.

2) 다음 도시로 이동하며 비교

다음 도시로 이동해서 이전 도시의 기름 가격과 현재 도시의 기름 가격을 비교합니다.

이때, 현재 도시의 기름 가격이 더 싸다면 1) 처럼 다음 도시까지 가는데 필요한 기름만 넣습니다.

만약, 현재 도시의 기름 가격이 비싸다면, 이전 도시의 기름 가격으로 기름을 넣습니다.

즉, 실제 운전을 하기 전, 시뮬레이션을 한다고 생각하면 좀 더 이해가 쉬울 것 같습니다.

주의점

여기에서 주의점은 제약 조건 입니다.

• 도시까지의 거리는 1 ≤ D ≤ 1,000,000,000
• 리터당 가격은 1 ≤ P ≤ 1,000,000,000

위 제약 조건을 생각한다면, 자료형 선택에 도움이 될 것입니다.

---

풀이

위의 접근법을 이해하셨다면, 문제 풀이는 금방 끝날 것이라고 생각됩니다.

최소 가격을 저장해 두었다가, 도시를 탐색하면서 갱신하면 됩니다.

#include <iostream>
using namespace std;

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

    int N;
    long long result = 0;
    cin >> N;

    int road[100000];
    int cities[100000];

    for (int i = 0; i < N - 1; i++)
        cin >> road[i];
    
    for (int i = 0; i < N; i++)
        cin >> cities[i];

    //다음 주유소까지 탐색하면서 가격을 비교하고, 비싸면 현재 주유소의 가격을 유지시킨다.
    long long bestPrice = cities[0];
    for (int i = 0; i < N - 1; i++)
    {
        if (cities[i] < bestPrice)
            bestPrice = cities[i];

        result += bestPrice * road[i];
    }

    cout << result;
}