BOJ 11399 | ATM

23238번 풀다가 도저히 생각이 안 나서 뇌풀기 겸으로 잠시 힐링했습니다.

i번 사람이 돈을 인출하는 데 필요한 시간은 $P_1+P_2+...+P_i$ 입니다.

그러므로 N번 사람까지 모두 인출하려면 $N×P_1 + (N-1)×P_2 + ... + P_N$ 이므로 작은 원소가 맨 앞으로 오도록 오름차순 정렬해주면 됩니다.

이후 누적합을 구하고 모든 누적합을 다 더해주면 정답입니다.

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

int main(){
	int N; cin >> N;
	vector<int> v;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	// prefix sum
	
	for (int i = 1; i < N; i++) v[i] += v[i-1];
	
	int sum = 0;
	for (int i = 0; i < N; i++) sum += v[i];
	cout << sum;
}