코딩테스트

[백준][Python] 1758 알바생 강호

yeeejji 2024. 3. 2. 14:57
728x90

그리디, 정렬 / 실버 4

☕️

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

 

1758번: 알바생 강호

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

www.acmicpc.net

 

N = int(input())
tips = []
ans = 0 

for _ in range(N):
    tips.append(int(input()))

tips.sort(reverse=True) # 내림차순 정렬

for i in range(0, len(tips)):
    tip = tips[i] - i
    if tip < 0:
        tip = 0
    ans += tip

print(ans)

 

받을 수 있는 팁의 최댓값: 팁을 가장 많이 주는 사람을 앞 순서에 배치해야 함.

즉, 팁을 내림차순 정렬한 뒤, 순서대로 등수를 매긴다.

팁의 값이 음수인 경우, 팁을 주지 않음 (tip = 0)