(Python) - BOJ(1758번) : 알바생 강호

 

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

1758번: 알바생 강호

---

• 해설 : 

줄을 서 있는 손님들이 입장하는 순서대로 강호에게 팁을 준다. 

원래 주려고 했던 팁이 10원이고 3번째로 들어갔다면 10 - (3 - 1) = 8원의 팁을 주게 된다.

손님들이 주려는 팁의 정보가 주어질 때 어떻게 줄을 세워야 가장 팁을 많이 받을 수 있는지 찾는 문제이다.

 

 

 

 

---

• 풀이 :

그리디하게 풀 수 있는 문제이다.  돈을 많이 주는 사람의 순으로 정렬하고 

받을 수 있는 팁이 1원 이상일 동안 계속 합해준다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
 
if __name__ == "__main__":
    N = int(input())
    tip = sorted([int(input()) for _ in range(N)],reverse=True)
    ans = 0
    for idx,tips in enumerate(tip):
        if tips - idx <= 0:
            break
        ans += tips - idx
    print(ans)