[백준][C++] 13305: 주유소

 

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

 

 

 

 

---

- 문제

 

 

 

위와 같이 도로의 길이가 간선 위에, 주유소 기름 가격이 원 내부에 주어지고 좌에서 우로 이동할때 끝에서 끝까지 가장 저렴하게 갈 수 있는 경우를 구하는 문제다. 

 

 

---

- 해설

 

쉽게 풀 수 있는 문제다.

 

도로의 길이가 

2 3 1

 

그리고 기름값이 

5 2 4 1

이라고 되어 있으면,

 

1. 첫번째 도시에 들렀을 때, 

 

지금까지 온 거리가 0이고 가장 싼 기름값이 5이므로

 

0 += 0 * 5가 된다.

 

2. 두 번째 도시에 들렀을 때

 

지금까지 온 거리가 2이고 두 번째 도시의 기름값이 5보다 싸므로

 

0+= 2 * 5를 해서

10이 되고, 기름값 2를 저장하자.

 

3. 세 번째 도시에 들렀을 때는 기름값이 더 비싸지므로 무시하고

 

4. 마지막 도시에 들렀을 때는 기름값이 얼마든 상관없으니, 이때까지 온 거리

3과 1을 여기까지 오면서 가장 쌋던 2의 기름값으로 구매를 하면

 

총 18원이 된다.

---

 

- 풀이

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, temp, least = 1000000001;
    vector<int> road;
    vector<int> gasStation;
    long long answer = 0, went = 0;

    cin >> N;
    for (int i = 0; i < N - 1; i++)
    {
        cin >> temp;
        road.push_back(temp);
    }
    for (int i = 0; i < N; i++)
    {
        cin >> temp;
        gasStation.push_back(temp);
    }
    // 여기까지는 입력

    for (int i = 0; i < N - 1; i++) // 마지막 도착지까지가 아닌 마지막 도로까지만 반복
    {
        if (least > gasStation[i]) // 현재까지 가장 싼 기름값보다 더 싼곳을 찾으면
        {
            answer += went * least; // 지금까지 온 거리만큼의 기름만 사고,
            went = 0;
            least = gasStation[i]; // 싼 기름 가격 저장
        }
        went += road[i]; // 더 싼 기름 찾을때까지 계속 도로 길이만큼 저장
    }
    answer += went * least; // 마지막 도착지까지의 거리는 위의 반복문에서 계산 못하니 추가로 계산
    cout << answer;

    return 0;
}

 

 

---

- 새롭게 알게 된 점