[백준] 1758 알바생 강호

문제

• 손님들이 줄을 서 있고 순서대로 커피를 하나씩 받고 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 준다.
• 팁 = 원래 주려고 생각했던 돈 - (반은 등수 - 1)
  만약 음수라면 팁을 주지 않는다.
• N명의 손님들의 원래 주려고 생각한 팁의 금액이 주어질 때, 순서를 적절히 바꿨을 때 팁의 최댓값 구하기
• 1 <= N <= 100,000

 

 

풀이

• 원래 주려고 했던 돈에서 (받은 등수 - 1) 만큼의 금액만큼 제외하게 된다.
  -> 전체 팁의 액수가 늘어나려면 (받은 등수 - 1)으로 줄어드는 금액을 최소화 시켜야 한다.
• 1원을 주려고 한 사람은 2번째로 가져가든, 10번째로 가져가든 0원의 팁을 준다.
  즉, 팁을 많이 주려고 했던 사람이 더 빠르게 커피를 가져가도록 한다.

 

N = int(input())
tips = [int(input()) for _ in range(N)]

tips.sort(reverse=True)
answer = 0
for i in range(N) :
    tip = tips[i] - i
    if tip > 0 :
        answer += tip
    else :
        break

print(answer)

 

References

• 백준 그리디