백준 13305 주유소 문제 c++

 

간단해 보이지만 막상 순서를 잘 조립하려면 N-1로 돌려야할지 N으로 돌려야할지 바로 안떠오를 수 있는 문제고 실제로 비슷한 난이도의 문제보다 오려걸렸고 서브태스크에 걸려 계속 틀린 문제. 이런 문제는 애초에 한 번 익숙해져 놔야 더 안틀릴 듯 하다.

 

이게 문제의 서브태스크인데 사실 문제 자체의 입력조건을 잘 신경써야 한다

 

 

개인적으로 이 문제의 핵심은 다음과 같다.

1. minCost가 등장 했을 때 대처로직

2. 최소값, 최대값에 유의한 개념

 

주유소 자체가 많이 주어져 시간 초과가 나는 문제인가? 생각을 하면서 괜한 시간에 신경을 썼는데 이는 for문으로 돌더라도 한 번만 돌기 때문에 O(n)의 시간복잡도를 가지기 때문에 시간초과가 날 일 자체가 없다.

 

 

제출했다가 틀린 답(이걸로 제출하면 17점을 받게 된다)

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

int n;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    long long diss[n];
    long long costs[n];
    for(int i=0; i<n-1; i++){
        cin >> diss[i];
    }
    for(int i=0; i<n; i++){
        cin >> costs[i];
    }

    long long totalCost = 0;
    long long minCost = 999;
    long long prefixDis = 0;
    for(int i=0; i<n-1; i++){
        if(costs[i] < minCost){// 이번 주유소가 더 싸면
            minCost = costs[i];
            totalCost += costs[i] * diss[i];
        }else{// 이번 주유소가 더 비싸면
            totalCost += minCost * diss[i];
        }
    }
    // 1. 5 <= 999
    // 1. total = 5*2
    // 2. 2 <= 5
    // 2. total = 10 + new Cost

    cout << totalCost;

    return 0;
}

 

맞은 답

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

int n;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    long long diss[n];
    long long costs[n];
    for(int i=0; i<n-1; i++){
        cin >> diss[i];
    }
    for(int i=0; i<n; i++){
        cin >> costs[i];
    }

    long long totalCost = 0;
    long long minCost = INFINITY;
    long long prefixDis = 0;
    for(int i=0; i<n-1; i++){
        if(costs[i] < minCost){// 이번 주유소가 더 싸면
            minCost = costs[i];
            totalCost += costs[i] * diss[i];
        }else{// 이번 주유소가 더 비싸면
            totalCost += minCost * diss[i];
        }
    }
    // 1. 5 <= 999
    // 1. total = 5*2
    // 2. 2 <= 5
    // 2. total = 10 + newCost

    cout << totalCost;

    return 0;
}