백준 알고리즘 파이썬(Python) 1758번 알바생 강호

---

이 문제의 핵심은 팁을 받은 순서를 큰 순서대로 리스트에 배열하는것 이다

 

만약 1, 1, 9, 9 가 주어진다 생각해보면 작은 숫자 즉 1이 줄의 뒤로가면 어느순간 돈 - (반은 등수 - 1) 의 값이 음수가 나온다. 따라서 1은 2번째 부터는 어디에 줄을 서든 어차피 팁은 0원이다

하지만 큰 숫자는 뒤로 갈수록 원래 주려고 했던 팁이 줄어든다. 즉 팁을 최대로 받을 수 있는 최적의 방법에서 멀어진다는 얘기다. 

그리디 알고리즘은 최적의 결과값을 도출해내는게 목적이다.

---

n = int(input()) #사람의 수 N이 주어짐
tip = [] #tip을 넣을 리스트 생성
for _ in range(n):
    a = int(input())
    tip.append(a) 
tip.sort(reverse = True) #줄 (선사람의 생각하는 팁을 받아와 큰 순서대로 배열

rate = 1 #등수 초기화
result = 0 #결과값 초기화
for i in tip:
    if (i - (rate-1)) >= 0: #(주려고생각한 팁 - (받은등수 - 1)) 이 음수가 아닌 경우만 알고리즘 생성
        result = result + (i - (rate-1))
        rate += 1
    else:
        continue
print(result)