[그리디/Greedy] 백준 1758 알바생 강호 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1758번: 알바생 강호

 

 

 

2. 문제 풀이

팁 + (1 - 순서)

 최대한 많은 팁을 얻어야 합니다. 순서가 늦어질수록 팁이 낮아지며, 음수가 되면 아예 받지 못합니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 자본주의대로 풀이하시면 됩니다. 더 많은 팁을 주는 손님부터 받습니다. 그래야 팁 손실을 줄일 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n = int(input())
tips = []
for _ in range(n):
    tips.append(int(input()))

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

# 팀 많이 주는 사람부터 주문 받기
res = 0
for idx, tip in enumerate(tips, 1):
    # 팁이 음수이면 0
    if tip + (1 - idx) < 0:
        pass
    else:
        res += tip + (1 - idx)
print(res)

 팁을 1만 주려고 했던 사람을 5순위로 미뤄도 1만 손해보게 되지만, 팁을 5만큼 주려고 했던 사람을 5순위로 미루면 5를 손해보게 됩니다.

 따라서 내림차순으로 정렬하고 팁을 받습니다.