※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
손님으로부터 받을 수 있는 돈은 정해져 있고, 등수가 뒤로 밀려날 수록 받을 수 있는 금액에서 1원씩 빠진 금액을 받게 됩니다. 즉, 빠지는 값이 고정적으로 정해진 상태에서 손님을 배치하는 문제입니다.
직감적으로 큰 돈을 가진 손님을 앞에 둘 수록 유리하다는 것을 알 수 있습니다. 왜냐하면, 큰 돈을 가진 손님을 뒤에 배치할 경우, 작은 돈을 가진 손님과 비슷해지거나 손해가 되기 때문입니다. 따라서 큰 돈을 받을 수 있는 손님부터 정렬하여, 실제로 받게 되는 돈을 계산하면 되는 문제입니다.
단, 10만명이 최대 10만원까지 팁을 줄 수 있으므로, 답의 최댓값이 int 범위를 넘어갈 수 있다는 점에 유의하세요.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
int w[100001];
int main()
{
int n;
long long ans = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> w[i];
sort(w, w + n);
for (int i = n - 1, j = 1; i >= 0; i--, j++)
{
int tip = w[i] - (j - 1);
ans += tip >= 0 ? tip : 0;
}
cout << ans;
}