본문 바로가기
알고리즘

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

by SiO2whocode 2021. 2. 24.
반응형

www.acmicpc.net/problem/13305

 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

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;
}
반응형

댓글0