백준(BOJ) 11399 ATM C++ 풀이

문제 링크: https://www.acmicpc.net/problem/11399

11399번: ATM

 

주어진 예시를 직접 손으로 한 번 써보면, 어떤 계단 형태의 합이 완성되는 것을 알 수 있다.

 

예를 들면, 가장 앞에 선 사람의 인출 소모 시간은 뒷 사람들의 소모 시간에 포함되기 때문에 지속적으로 전체 소모 시간을 구하는 과정에서 합해지는 것이다.

 

말이 어려운데 정답부터 이야기하자면, 결국 인출에 소모되는 시간이 긴 사람은 뒤쪽에 서 있는 것이 좋다는 것이다.

 

인출에 소모 시간이 긴 사람이 내 앞에 서 있다면, 내가 대기해야하는 시간이 길어지는 것은 자명하기 때문이다.

 

따라서 주어진 Pi들을 오름차순으로 정렬하고, 누적합을 구하면 쉽게 풀 수 있다.

 

/* BOJ 11399 ATM */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int n, arr[1001];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    sort(arr + 1, arr + 1 + n);
 
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            ans += arr[j];
 
    cout << ans << endl;
 
    return 0;
}