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

 📚 문제

[BOJ C++] 백준 13305번: 주유소
https://www.acmicpc.net/problem/13305

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 각 도로의 길이와 리터당 가격은 최대 1,000,000,000이므로 정수형 자료형은 long long을 사용해야 한다.

• 최소 비용으로 제일 오른쪽의 도시로 이동하기 위해서는, 각 구간에서의 최소 비용으로 기름을 넣고 이동해야한다. 따라서 구간별로 현재 도시까지의 최저 기름 가격을 저장하고, 그 가격을 기준으로 다음 도시로 이동하는 것을 반복하면 최적의 가격을 갱신하며 최소 주유 비용을 구할 수 있다. 즉, 그리디 알고리즘을 활용하여 문제를 해결할 수 있다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<long long> len(n - 1), oil(n); // len: 각 도로의 길이 저장, oil: 각 도시의 리터당 기름 가격 저장.
    for (int i = 0; i < n - 1; i++) cin >> len[i];
    for (int i = 0; i < n; i++) cin >> oil[i];
    
    long long price = oil[0]; // 최소 기름 가격 저장.
    long long total_cost = 0; // 총 비용 계산.
    
    for (int i = 0; i < n - 1; i++) {
        price = min(price, oil[i]); // 현재까지의 최소 기름 가격 갱신.
        total_cost += price * len[i]; // 최소 가격으로 도로 이동 비용 계산.
    }
    
    cout << total_cost << '\n';
    return 0;
}