BOJ 11399번 : ATM

문제를 읽자마자 그냥 오름차순으로 정렬한 후에 더하는 것만 하면 된다고 생각했다.

하지만 실버3인데 이렇게 그냥 가는 거라고...? 라는 생각을 하면 그냥 제출 해버렸고.....

맞아 버렸다...

 

이 문제는 그리디알고리즘 보다는 그냥 정렬 알고리즘 여러개 공부할때 사용하는 문제 인것 같다.

 

<Solution>

단순히 생각하면 내 앞사람까지 걸린 시간이 제일 적으면 된다.

그러기 위해서는 내 앞사람이 나보다 인출하는 시간이 적으면 된다.

그러므로 오름차순 정렬을 한 후, 각 인덱스 별로 더하기를 진행하면 끝!

 

<소스코드>

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
 
int main() {
 
    int n, res;
    cin >> n;
    vector<int> v(n);
    vector<int> add(n);
    
    for (int i = 0; i < n; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    add[0] = v[0];
    res = v[0];
    for (int i = 1; i < n; i++) {
        add[i] = add[i - 1] + v[i];
        res += add[i];
    }
    cout << res;
 
}

 

<문제>

www.acmicpc.net/problem/11399

11399번: ATM