[c++][Greedy] 백준 13305번 문제 풀이

알고리즘

 

도시를 하나 씩 옮겨가면서

첫 번째 도시~ 현재 도시 중 가장 주유 값이 적은 것을 선택한다.

현재도시~다음 도시 까지의 도로의 길이를 구한다.

(첫 번째 도시 ~ 현재도시 중 가장 적은 주유값) * (현재도시~다음 도시 까지의 도로의 길이) 를 total에 더한다.

이 과정을 첫 번째 도시 부터 마지막 도시까지 적용하면 쉽게 구할 수 있다.

 

Coding

#include <iostream>
#include <vector>

using namespace std;

int main(int args ,char** argv){

    int N ;
    long long int temp;

    cin >> N;

    vector<long long int> street;
    vector<long long int> cost_gas;

    for(int i = 0 ; i < N-1 ; ++i){
        cin >> temp;
        street.push_back(temp);
    }
    
    for(int i = 0 ; i < N; ++i){
        cin >> temp;
        cost_gas.push_back(temp);
    }

    long long int min_in_range = cost_gas[0];
    long long int total = min_in_range * street[0];

    for(int i = 1 ; i < N-1 ; ++i){
        if(min_in_range > cost_gas[i]) min_in_range = cost_gas[i];
        total += (street[i] * min_in_range);
    }

    cout << total;
}

 

※ 주의할 점

 

입력 값이

N은 200,000 까지 이지만

리터당 주유값 과 거리는  1,000,000,000 이하 이므로, long long int를 사용해 줘야 한다.

 

 

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

13305번: 주유소