[C++] 백준 온라인 저지 13305번 주유소 풀이

가장 마지막 마을까지 가는데 필요한 최소 주유 금액을 구하는 문제

 

---

문제의 조건

 

1. 도시의 개수 N이 주어진다. 도시들은 일직선상에 있기 때문에 무조건 맨 앞 도시부터 차례대로 가야 한다. 

 

2. 처음엔 차에 기름이 없기 때문에 맨 처음 도시에서 기름을 넣고 출발해야 한다. 

기름통의 크기에는 제한이 없다. 

도시 간 도로를 이용하여 이동할 때 1km당 1리터를 사용한다. 

 

3. 각 도시에는 주유소가 하나씩 있으며 각 도시마다 기름 가격이 다를 수 있다. 

그렇기 때문에 다른 도시보다 기름 가격이 싼 도시에서 최대한 넣고 가는 것이 이득이다. 

 

4. 각 도시에 있는 주유소의 리터당 기름 가격과 각 도시 간 거리가 주어질 때 마지막 도시까지 가는데 필요한 최소 주유 금액을 구해서 출력하기 

 

---

풀이 과정

 

처음엔 기름이 없기 때문에 첫번째 도시에서는 무조건 주유를 해야 합니다. 

그래서 두번째 도시부터 기름 가격을 선택할 수 있기 때문에 처음에 기름을 넣은 도시보다 가격이 싼 도시가 언제 나오는지 구한 다음

그 도시에 도착하기까지 걸리는 거리만큼만 기름을 넣은 다음에

두번째로 가격이 싼 도시에 도착하면 또 더 싼 도시를 탐색한 후 또 그 도시까지 걸리는 거리만큼만 기름을 넣고.... 를 반복하면 될 거 같다는 생각을 했습니다. 

 

정리

1. 첫번째 도시의 기름 가격을 가장 싼 가격으로 저장하고 첫번째-두번째 도시까지 이동 거리를 현재 이동해야 하는 거리로 저장해놓고 시작한다. 

 

2. 반복문으로 도시별 기름 가격을 저장한 배열의 1번째 인덱스부터 탐색하면서 현재 최저가보다 싸다면 

이동해야 하는 거리 * 최저가 를 정답에 더해주고

현재 최저가를 새롭게 찾은 최저가로 갱신한다. (최저가 도시까지는 이전 최저가로 이동해야 하기 때문)

 

3. i번째 도시가 현재 최저가보다 비싸다면 이동해야 하는 거리를 더해준다. 

 

4. 마지막 도시의 가격은 확인할 필요가 없기 때문에 N-2보다 적을 때 까지 2, 3번 과정을 반복하다가 반복문이 끝나면 마지막 도시까지의 이동거리를 최저가와 곱한 값을 정답에 더해준 후 출력한다. 

 

---

 

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[])
{
    long N; //오버플로 방지용 (첨에 int형으로 해서 58점 받았다가 long으로 바꾸고 100점 받음 ㅠㅠ)
    cin >> N;
    
    //도시간 거리 배열
    vector<long> distance;
    for (int i = 0; N - 1 > i; i++)
    {
        int d;
        cin >> d;
        distance.emplace_back(d);
    }
    
    //도시별 기름 가격 배열 
    vector<long> price;
    for (int i = 0; N > i; i++)
    {
        int p;
        cin >> p;
        price.emplace_back(p);
    }
    
    long answer = 0;
    //시작 최저가는 첫번째 도시 가격 
    long lowest = price.front();
    //최초 이동거리는 첫번째-두번째 도시간 이동거리(즉 거리 배열의 0번째 인덱스)
    long partOfDistance = distance.front();
    for (int i = 1; price.size() - 1 > i; i++)
    {
        //현재 최저가보다 i번째 도시의 가격이 더 싸면 
        if (price[i] < lowest)
        {
            //현재 최저가와 i번째 도시까지의 이동거리를 곱한 값을 정답에 더해준다. 
            answer += lowest * partOfDistance;
            //최저가를 i번째 도시의 가격으로 갱신한다. 
            lowest = price[i];
            //i번째 도시와 i+1번째 도시까지의 이동거리를 새롭게 이동해야 하는 거리로 바꿔준다. 
            partOfDistance = distance[i];
        }
        else
        {
            //i번째 도시가 현재 최저가보다 비싸면 이동해야 하는 거리만 더해준다. 
            partOfDistance += distance[i];
        }
    }
    
    //위 반복문이 끝나면 마지막 도시까지의 이동 가격은 계산하지 않고 끝나기 때문에 마지막으로 더해준다. 
    answer += lowest * partOfDistance;
    
    cout << answer;
    
    return 0;
}