[백준 13305] 알고리즘 91일차 : 주유소

www.acmicpc.net/problem/13305

13305번: 주유소

C++ 그리디 알고리즘

좀 쉬어가려고 그리디 풀었는데 그리디 무려 5개월만에 풀어서 좀 낯설었다.

 

접근방법

지금까지의 최저가를 갖고 가다가 그 최저가 보다 더 적은 값을 만나면

거기까지는 지금까지의 최저가로 주유해서 간 다음 그 이후부턴 그 주유소에서 주유하는 식

 

오답노트

거리랑 금액이 모두 최대가 int최대범위여서

total금액과 중간중간 거리를 더하는 변수는 long long 타입을 써줘야한다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int dist[n-1];
    for(int i = 0 ; i < n-1 ; i++){
        cin >> dist[i];
    }
    int price[n];
    for(int i = 0 ; i < n ; i++){
        cin >> price[i];
    }
    int minPrice = price[0];
    int minIndex = 0;
    long long totalPrice = 0;
    for(int i = 0 ; i < n ; i++){
        if(price[i] < minPrice || i == n-1){
            long long sumOfdist = 0;
            for(int j = minIndex ; j < i ; j++){
                sumOfdist += dist[j];
            }
            totalPrice += sumOfdist*minPrice;
            minPrice = price[i];
            minIndex = i;
        }
    }
    cout << totalPrice;
    return 0;
}