BOJ 1758번: 알바생 강호

www.acmicpc.net/problem/1758

1758번: 알바생 강호

문제풀이:

각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다.

라고 했으므로 원래 주려고 생가가했던 돈이 큰 순서대로 먼저 주면 받을 수 있는 팁이 최댓값이 될 것이다.

 

import sys

N = int(sys.stdin.readline())
tip = []
for _ in range(N):
    tip.append(int(sys.stdin.readline()))

tip.sort(reverse = True)
ans = 0
for i in range(1,N+1):
    cost = tip[i-1] - (i-1)
    if (cost>0):
        ans += cost
    else:
        break
    
print(ans)