boj 1758 : 알바생강호

문제 주소: https://www.acmicpc.net/problem/1758

난이도: silver 4

1.문제설명

• 가게 입장시간이 정해져있다.
• 가게 입장시간전에 손님들을 줄 새워서 한번에 입장시킨다.
• 이때 손님들은 각자 원래 주려고 생각해둔 팁의 액수가 있다.
• 주려고 생각해둔 액수 - (받은등수 - 1) 만큼 팁을 준다. 음수가되면 0원을 준다
• 알바생이 손님의 위치를 임의로 바꿀수있을때
• 최대로 얼마를 팁으로 받을수 있을까?

2.문제해결 아이디어.

• 직관적으로 그리디다.
• 음수가되면 0 이기때문에 -100이건 -1이건 다 0원이다.
• 즉 큰 가치를 가진 고객이 우선이다.
• 왜냐면 큰 가치를 가진 고객은 순서가밀리면 점점 가치가 떨어지지만
• 작은 가치를 가진 고객은 어느순간 가치의 변화가 0원에서 멈추고, 금방 0원이된다.

3.문제접근법

• 내림차순으로 sorting한다.
• 그다음 팁 계산방식을 그대로 사용해서 정답에 더해간다.

4.특별히 참고할 사항

• 없다.

5.코드구현

N = int(input())
line = []
for i in range(N):
    line.append(int(input()))
line.sort(reverse=True)
ans = 0
for i in range(N):
    temp = (line[i] - i)
    if temp < 0:
        temp = 0
    ans += temp
print(ans)