[baekjoon] 백준 1758번(파이썬): 알바생 강호

문제

1758번: 알바생 강호

 

- 스타박스에서는 손님을 8시가 될 때 까지, 문앞에 줄 세워 놓는다.

- 그리고 8시가 되는 순간 손님들은 모두 입구에서 커피를 하나씩 받고, 자리로 간다.

- 강호는 입구에서 커피를 하나씩 주는 역할을 한다.

- 손님들은 입구에 들어갈 때, 강호에게 팁을 준다.

- 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다.

- 각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

- 예를 들어, 민호는 팁을 3원 주려고 했고, 재필이는 팁을 2원, 주현이가 팁을 1원 주려고 한 경우를 생각해보자.

- 민호, 재필, 주현이 순서대로 줄을 서있다면, 민호는 강호에게 3-(1-1) = 3원, 재필이는 2-(2-1) = 1원, 주현이는 1-(3-1) = -1원을 팁으로 주게 된다. 주현이는 음수이기 때문에, 강호에게 팁을 주지 않는다. 따라서, 강호는 팁을 3+1+0=4원을 받게 된다.

- 스타박스 앞에 있는 사람의 수 N과, 각 사람이 주려고 생각하는 팁이 주어질 때, 손님의 순서를 적절히 바꿨을 때, 강호가 받을 수 잇는 팁의 최댓값을 구하는 문제이다.

- 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작은 자연수이다.

- 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수이다.

알고리즘

- 사람 수를 입력받는다.

- 사람이 내는 돈을 입력받아 리스트에 넣는다.

- 돈을 많이 내는 사람부터 팁을 받기 위해 내림차순으로 정렬한다.

- 사람 수 만큼 반복하여 팁을 받는다.

- 팁이 0보다 크면 팁을 받고 아니라면 팁을 받지않는다.

- 팁을 모두 더해 출력한다.

코드

import sys

n = int(sys.stdin.readline())
money = [int(sys.stdin.readline()) for _ in range(n)]
# 돈을 많이 내는 사람부터 팁을 받기 위해 내림차순으로 정렬
money.sort(reverse= True)
result = 0
# 사람 수 만큼 반복하여 팁을 받는다.
for i in range(n):
    # 사람이 내는 돈 - (받은 등수 - 1) 
    # (받은 등수 - 1) = 0번째로 시작하는 순서와 같다. (0, 1, 2, 3,..)
    tip = money[i] - i
    
    # 팁이 0 보다 크면 팁을 받고 아니면 팁을 받지 않는다.
    if tip > 0:
        result += tip
        
# 팁을 모두 더해 출력
print(result)

결과

위 코드에서 if문 바로 위에 print(tip)을 작성하게되면 얼마에 팁을 주려고 하는지 다음 출력화면과 같이 확인할 수 있다.

<출력화면>

위 출력화면을 보게되면 3원을 냈을 때 3 - (받은 등수 -1)을 한 값을 팁으로 주는 것을 알 수 있다. 이때 (받은등수 -1)은 0, 1, 2, 3..으로 규칙이 있는 것을 알 수 있고 반복문에 i도 0, 1, 2, 3.. 으로 바뀌는 것을 확인할 수 있다. 즉, i와 똑같이 (받은등수 -1)이 바뀌는 것을 알 수 있다. 따라서 돈을 많이 내는 사람부터 내림차순으로 정렬하고 그 사람이 내는 돈 - i를 했을 때 팁을 받을 수 있는 돈의 최대가 되는 것이다. 

github

junjange/CodingTest