[백준][Python] 1758 알바생 강호

그리디, 정렬 / 실버 4

☕️

https://www.acmicpc.net/problem/1758

1758번: 알바생 강호

 

N = int(input())
tips = []
ans = 0 

for _ in range(N):
    tips.append(int(input()))

tips.sort(reverse=True) # 내림차순 정렬

for i in range(0, len(tips)):
    tip = tips[i] - i
    if tip < 0:
        tip = 0
    ans += tip

print(ans)

 

받을 수 있는 팁의 최댓값: 팁을 가장 많이 주는 사람을 앞 순서에 배치해야 함.

즉, 팁을 내림차순 정렬한 뒤, 순서대로 등수를 매긴다.

팁의 값이 음수인 경우, 팁을 주지 않음 (tip = 0)