[Greedy] 백준 13305번 "주유소" C++ 풀이

문제 링크

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

풀이

• 예제 그림

  

• 문제는, 현재 도시의 주유 가격이 다음 도시의 주유 가격보다 비싼지, 저렴한지에 따라 나뉘게 됩니다.

• 현재 주유소보다 다음 주유소가 싸다면,

• 현재 주유소에서는, 다음 주유소로 이동하는 데에 걸리는 거리만큼만 주유하고, 다음 주유소에서 더 주유하는 것이 이득입니다.

• 만약, 현재 주유소가 다음 주유소보다 싸다면,

• 다음 주유소에서 다다음 주유소까지 이동하는 데에 걸리는 거리만큼, 현재 주유소에서 더 주유하는 것이 이득입니다.

• 즉, 도시를 이동할 때마다 기름을 채워주되,

• 이전에 등장했던 주유 가격 중 가장 최소의 가격으로 기름을 채울지, 현재 주유소의 가격으로 기름을 채울지만 정하면 됩니다.

주의 사항

• 첫 번째 도시에서 두 번째 도시로 이동할 경우, 어떤 경우이던지 간에, 첫 번째 도시에서 주유해야합니다.
• 마지막 지점의 기름값은 무시해도 됩니다.
• 도시간 거리와 도시별 기름값의 범위는 1 ~ 1,000,000,000 이므로, 각각 long long 타입을 사용해야합니다.
  • 결과값 또는 함수 반환 타입도 잘 확인해서 long long 형으로 맞춰줘야합니다.

코드

#include <iostream>
#include <vector>

using namespace std;

// 도시 별 도로의 길이
vector<long long> road;

// 도시 별 주유 가격
vector<long long> oil;

// 최소 누적 비용
long long total_oil_cost;

// 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는, 최소 비용 계산
long long greedy(){

    // 우선, 첫 번째 도시의 주유 비용을 최소 주유 비용으로 지정
    long long min_oil_cost = oil[0];

    // 첫 번째 도시에서 두 번째 도시로 갈때에는, 반드시 첫 번째 도시에서 주유
    // 따라서, 두 번째 도시까지는 주유를 마친 상태
    total_oil_cost += oil[0] * road[0];

    // 두 번째 도시부터 제일 오른쪽 도시까지, 도시 별 주유 가격을 확인
    for (int i=1; i<oil.size()-1; ++i){

        // i 번째 도시의 주유 가격이, 현재까지의 최소 주유 비용보다 비싸다면, 
        if (oil[i] > min_oil_cost){
            // 현재까지의 최소 주유 비용으로, i+1 번째 도시까지 이동할 수 있도록 주유
            total_oil_cost += min_oil_cost * road[i] ;
        }

        // i 번째 도시의 주유 가격이, 현재까지의 최소 주유 비용보다 싸다면, 
        else{
            // i 번째 도시의 주유 가격을, 최소 주유 비용으로 변경한 뒤,
            min_oil_cost = oil[i];
            // 최소 주유 비용으로, i+1 번째 도시까지 이동할 수 있도록 주유
            total_oil_cost += min_oil_cost * road[i] ;
        }
    }

    // 최소 누적 비용 반환
    return total_oil_cost;
}

int main(){

    // 도시 개수
    int n;
    cin >> n;

    // 도시 별 도로의 길이
    for (int i=0; i<n-1; ++i){
        long long road_len;
        cin >> road_len;
        road.push_back(road_len);
    }

    // 도시 별 주유 가격
    for (int i=0; i<n; ++i){
        long long oil_cost;
        cin >> oil_cost;
        oil.push_back(oil_cost);
    }

    // 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용 계산
    cout << greedy() << endl;

}

참고

• https://beginnerdeveloper-lit.tistory.com/31
• https://ongveloper.tistory.com/327?category=854013
• https://excited-hyun.tistory.com/71