[ baekjoon ] #13305 주유소

백준 #13305 주유소

문제 요약

---

• 제일 왼쪽 도시 → 오른쪽 도시
• 도시 사이의 도로들은 길이가 다를 수 있음
• 처음 출발할 때 기름 없어서 넣고 출발해야함
• 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용 구하기 !

💡Idea

1. 처음엔 무조건 기름을 넣어주자 !
2. 어떤 기준으로 기름을 넣을까?
   - 기름이 제일 싼 곳이 아니면 가야할 만큼만 넣자
   → 이때 만약 나중에 나오는 주유소가 더 비싼 경우 처리를 못함,,
   - 지나온 주유소의 가격과 비교하자

[ SourceCode ]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N; // 도시의 개수
    long long expense = 0; // 총 요금
    cin >> N;

    vector <long> distance(N - 1); // 다음 도시까지의 거리
    vector <long> oil_fee(N); // 주유 요금

    for(int i=0; i<N - 1; i++) {
        cin >> distance[i];
    }

    for(int i=0; i<N; i++) {
        cin >> oil_fee[i];
    }

    expense += distance[0] * oil_fee[0];
    long long min_fee = oil_fee[0];

    for(int i=1; i<N - 1; i++) {
        if(min_fee > oil_fee[i]) {
            min_fee = oil_fee[i];
        }
        expense += distance[i] * min_fee;
    }

    cout << expense;

    return 0;
}

Feedback

---

1. 습관적으로 int로 만들어서 틀림,,
   → 거리와 요금의 범위를 보면 1이상 1,000,000,000 이하이기 때문에 최대 10억이므로 long을 써야한다.
   → 자료형의 타입을 잘 생각하자 !!!
2. 문제를 조금 더 단순하게 생각하는 연습하기 !
3. greedy 문제를 많이 풀어볼 것