[백준 알고리즘/C++] 11399 ATM

 

 

한 대의 ATM 앞에 n명의 사람이 기다리고 있다

총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우 (i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분)

 [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다

2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다

이렇게 3, 4, 5번 까지 돈을 뽑으면 총 39분이 걸리는데, 줄 서는 순서를 잘 바꾸면 대기시간이 시간이 줄어든다

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 문제!

 

 

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면 가장 빠르게 모든 사람이 인출할 수 있는데

이 순서는 인출할 때 걸리는 시간이 짧은 순이다

그러므로 Pi를 기준으로 정렬하여 계산해주면 된다

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, arr[1000], sum[1000];
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + n);
 
    int res;
    res = sum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + arr[i];
        res += sum[i];
    }
 
    cout << res;
}