[코딩테스트 C++] 주유소

오늘의 문제

주유소

접근방식

• 가장 적은 돈을 내려면, 값이 제일 싼 곳에서 주유를 해야한다.
• 따라서 앞으로 갈 경로 중에서 더 싼 값이 나올 때까지 최소로 주유해야한다.
• 더 큰 값이 나오면, 거리를 누적하여 더 싼 값이 나올 때 가장 작은 가격(맨 처음 값이겠지)에 누적된 거리값을 곱해준다.
• 여기서 주의해야할 점은 입력이 상당히 크다 1이상 1,000,000,000 이하이므로 값을 누적하면 Integer 범위를 자연스럽게 넘어가므로 long long 으로 선언해야한다.

나의 풀이

#include <stdio.h>
#include <iostream>

using namespace std;
int n;
const int MAX = 100000;
int len[MAX];
int price[MAX];

long long solution(){
    long long answer = 0;
    int mini = price[0];
    long long deposit = len[0];
    for(int i=1;i<n-1;i++){
        if(price[i]<mini){
            answer+= mini * deposit;
            deposit = len[i];
            mini = price[i];
        }else{
            deposit += len[i];
        }
    }
    return answer+ mini * deposit;
}

다른 풀이

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int V[100005];
ll D, m = 2e9, L;
int n;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++) cin >> V[i];
    for(int i = 0; i < n; i++){
        cin >> L;
        D += m * V[i];
        m = min(m, L);
    }
    cout << D << '\n';
}

배울 점

• m만 갱신해주면 되겠구나. 같은 방법이지만 메모리 사용이 훌륭하다. 누적을 할 필요가 없다.