[백준_python] 1758_알바생강호

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

1758번: 알바생 강호

문제

스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다.

스타박스에서는 손님을 8시가 될 때까지, 문 앞에 줄 세워 놓는다. 그리고 8시가 되는 순간 손님들은 모두 입구에서 커피를 하나씩 받고, 자리로 간다. 강호는 입구에서 커피를 하나씩 주는 역할을 한다.

손님들은 입구에 들어갈 때, 강호에게 팁을 준다. 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다. 각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

입력

첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수이다.

문제 해결

강호가 받을 수 있는 최댓값을 출력하는 문제이다. 받는 팁이 최댓값이 되려면 주려고 생각한 팁과 받은 등수가 반비례하면 되기에

그리디적인 해법으로 팁이 높을수록 빠른 순서에 배치를 하면 된다. 전형적인 그리디 문제 같다.

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
arr.sort(reverse=True)
res = 0
for i in range(n):
    if arr[i]-i>0:
        res += arr[i]-i
print(res)