Python으로 푸는 백준 1758. 알바생 강호

백준  1758.  알바생 강호

 문제는 간단한 문제인데도 정답 비율이 40%도 안되는 문제이다.

카페를 기다리는 대기줄 순위에 따라서 본래 알바생 강호가 받을 수 있었던 팁이 일정 규칙에 따라 줄어들기 때문에

손님이 지불하려고 하는 팁이 주어졌을 때,

손님의 순서를 적절히 바꿔 강호가 받을 수 잇는 팁의 최댓값을 구하는 문제이다.

문제 보러 가기

github에서 코드 보기

문제에서 제시한 조건

각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다.

만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

강호는 손님의 순서를 마음대로 바꿀 수 있다.

문제 풀이 방법

최대 이익을 얻기 위해서는 팁이 가장 많은 사람이 가장 먼저 입장시키면 된다.

따라서 파이썬에 내장된 정렬 메소드만 잘 활용하면 되는 문제이다. 

파이썬 코드

# 알바생 강호 (1758)
 
import sys
 
def greedy(tipList):
    total_tip = 0
    for idx, tip in enumerate(tipList):
        real_tip = tip - ((idx + 1) - 1)
        if real_tip <= 0:
            break
        total_tip += real_tip
    return total_tip
 
 
if __name__=="__main__":
    n = int(sys.stdin.readline().strip())
    tipList = []
    for i in range(0, n):
        tip = sys.stdin.readline().strip()
        tipList.append(int(tip))
    tipList.sort(reverse=True)
    print(greedy(tipList))
 

#백준 1758 알바생 강호 #파이썬 1758 알바생 강호 #python 1758 알바생 강호 #1758 알바생 강호 python #백준 알바생 강호 #백준 알바생 강호 python #그리디 알고리즘 #백준 그리디 알고리즘