[Algorithm] 백준 13305 주유소 c++

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

13305번: 주유소

 

풀이

Greedy

• 제일 왼쪽 도시의 주유 가격을 현재 가격으로 설정한다.
• n 번째 도시에서 n + 1 번째 도시로 넘어가기 위한 거리만큼 주유를 해서 비용을 누적한다.
• n + 1 번째 도시의 비용이 더 저렴한 경우 현재 가격을 n + 1 번째 도시의 주유 가격으로 업데이트한다.
• 주의) 데이터 타입을 long long으로 해야 한다! 

 

소스코드

#include <iostream>
#include <vector>
using namespace std;

vector<long long> lens;
vector<long long> costs;

int main(){
    int n, len, cost;
    long long ans = 0;

    cin>>n;
    for(int i=0; i<n-1; i++){
        cin>>len;
        lens.push_back(len);
    }
    for(int i=0; i<n; i++){
        cin>>cost;
        costs.push_back(cost);
    }

    int curCost = costs[0];
    for(int i=1; i<n; i++){
        ans += (curCost * lens[i-1]);
        //다음 도시의 비용이 더 저렴한 경우 cost 업데이트
        if(curCost > costs[i]) curCost = costs[i];
    }

    cout<<ans;

    return 0;
}

 

🤐 사족

처음에는 lens와 const, ans의 데이터 타입을 int로 했었다. 이렇게 하면 58점만 받게 된다. 입력받을 수 있는 값이 1,000,000,000이므로 int로는 부족하다는 것을 미리 알았다면 좋았을 것을.. 다음부터 데이터 타입의 범위를 잘 파악하자!