11399번

11399번 - ATM

그리디 알고리즘으로 줄을 어떻게 세울지 결정하는 문제이다.

시간이 가장 적게 걸리는 순으로 짜면 된다.

i 번째 사람이 걸리는 시간을 T[i] 라고 하면

T[1]=P[1]

T[2]=P[1]+P[2]

T[3]=P[1]+P[2]+P[3]

.....

T[i]=P[1]+P[2]+P[3]+....+P[i] 가 된다.

그래서 T 의 전체 합이 최소로 만들기 위해서는 가장 많이 중복되는 수가 가장 적은 수가 되어야 한다.

그래서 그냥 sort를 통해 오름차순으로 정렬하고 합을 구했다.

증명)

시간이 가장 적게 걸리는 사람 순이 아닌 최적의 답이 있다고 가정해보자.

그게 A B C 라고 해보자.

그리고 시간이 가장 적게 걸리는 사람 순으로 세운 답이 B C A 라고 해보자. 그러면 B<C<A 가 된다.

여기서 총 걸리는 시간을 비교해보면 ABC 의 경우에는 3*A+2*B+C 가 되고 BCA의 경우엔 3*B+2*C+A 가 된다.

이 둘을 빼보면 2A-B-C 가 되고 이는 A-B+A-C 가 되는데 이는 앞의 B<C<A 조건에 의해서 A-B>0, A-C>0 이므로 

앞에 시간이 더 많이 걸리는 것을 알 수 있다.

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int main()
{
    int N, ans = 0;
    int P[1001];
 
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> P[i];
    }
 
    sort(P, P + N);
 
    for (int i = 0; i < N; i++)
    {
        ans += (N - i)*P[i];
    }
 
    cout << ans << endl;
    return 0;
}