[백준] 1758번: 알바생 강호

1758번

문제

손님들은 입구에 들어갈 때 강호에게 팁을 준다. 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다.
각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

예를 들어, 민호는 팁을 3원 주려고 했고, 재필이는 팁을 2원, 주현이가 팁을 1원 주려고 한 경우를 생각해보자.

민호, 재필, 주현이 순서대로 줄을 서있다면, 민호는 강호에게 3-(1-1) = 3원, 재필이는 2-(2-1) = 1원, 주현이는 1-(3-1) = -1원을 팁으로 주게 된다. 주현이는 음수이기 때문에, 강호에게 팁을 주지 않는다. 따라서, 강호는 팁을 3+1+0=4원을 받게 된다.

강호가 받을 수 있는 팁의 최대값을 구하라.

어떻게 풀면 좋을까?

💡 정렬

주려고 했던 돈 - (받은 등수 -1) 이라고 했으니까, 주려고 했던 돈이 가장 커야 한다.
또한 (받은 등수 -1)이 가장 작아야 하겠다. 그래야 최대한 음수가 안나오면서도, 가장 큰 값이겠다.

풀이

N = int(input())
tips = [int(input()) for i in range(N)]
result = 0

# 내림차순으로 정렬함으로써 큰 값부터 처리시작
for i, tip in enumerate(sorted(tips, reverse=True)):
    if tip - i > 0:
        result += tip - i
print(result)