알고리즘💻/그리디
BOJ 1758번: 알바생 강호
호프
2021. 4. 6. 02:16
1758번: 알바생 강호
첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수
www.acmicpc.net
문제풀이:
각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다.
라고 했으므로 원래 주려고 생가가했던 돈이 큰 순서대로 먼저 주면 받을 수 있는 팁이 최댓값이 될 것이다.
import sys
N = int(sys.stdin.readline())
tip = []
for _ in range(N):
tip.append(int(sys.stdin.readline()))
tip.sort(reverse = True)
ans = 0
for i in range(1,N+1):
cost = tip[i-1] - (i-1)
if (cost>0):
ans += cost
else:
break
print(ans)