[백준,c++] 13305번 - 주유소

문제

13305번: 주유소

 

코드

17점짜리 코드

#include <iostream>
#include <vector>

using namespace std;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    vector<int> cost(N);
    vector<int> dist(N-1);
    
    int all_dist = 0;
    int index = 0, min_cost = 1e9+1;
    
    for(int i=0; i<N-1; i++){
        cin>>dist[i];
        all_dist += dist[i];
    }
    
    for(int i=0; i<N; i++){
        cin>>cost[i];
        if(cost[i]<min_cost && i != N-1){
            min_cost = cost[i];
            index = i;
        }
    }
    
    int ans = 0;
    
    for(int i=0; i<N-1; i++){
        if(i != index){
            int money = cost[i]*dist[i];
            ans += money;
            all_dist -= dist[i];
        }
        else{
            int money = cost[i]*all_dist;
            ans += money;
            break;
        }
    }
    cout<<ans;
    
}

 

100점짜리 코드

#include <iostream>
#include <vector>
#define ull unsigned long long

using namespace std;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ull N; cin>>N;
    ull ans = 0, min_cost = 1e9+1;
    vector<ull> cost(N);
    vector<ull> dist(N-1);
    
    for(int i=0; i<N-1; i++) cin>>dist[i];
    for(int i=0; i<N; i++) cin>>cost[i];
    
    for(int i=0; i<N-1; i++){
        min_cost = min(cost[i],min_cost);
        ans += min_cost * dist[i];
    }
    
    cout<<ans;

    
}

 

회고

오늘 부터 코딩 테스트를 대비하여 시간을 재면서 문제를 풀어보기로 결심했습니다. 그래서 시간을 재고 한번 풀어보았는데 17점까지 코드까지는 28분 만에 풀어서 나름 선방했다고 생각했는데 100점짜리 코드까지는 대략 60분이 걸렸습니다. 이렇게 단순한 그리디 문제였는데 왜 번뜩 생각이 나지 않았을까.. 맞추더라도 시간이 이 정도 걸리면 아무 소용없을 것 같은데 참.. 더 노력해야겠습니다.