백준 11399번 : ATM

문제 접근

---

이 문제는 부분합의 총합이 최소가 되게 하는 문제이다. x 번 사람이 대기하는 시간을 Px 라고 할 때 5명이 대기한다면 부분합의 총합 Ans = 5*P1 + 4*P2 + 3*P3 + 2*P4 + 1*P5 이다. 따라서 n 에 대해 Pn = n*P1 + (n-1)*P2 + (n-2)*P3 + ... + 2*P(n-1) + 1*Pn 이라고 할 수 있다. 고로 작은 순으로 정렬한 뒤 부분합의 총합을 구하면 끝!

 

 

문제 코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	int N, ans;
	cin>>N;
	vector<int> P(N);
	
	for(int i=0; i<N; ++i)
		cin>>P[i];
	
	sort(P.begin(), P.end());
	
	ans = P[0];
	
	for(int i=1; i<N; ++i)
	{
		P[i]+=P[i-1];
		ans += P[i];
	}
	
	cout<<ans<<'\n';
}