[백준] 1758번: 알바생 강호 (python)

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보다 작거나 같은 자연수이다.

 

 

출력 :

강호가 받을 수 있는 팁의 최댓값을 출력한다.

 

 

 

 

 

 

 

풀이)

처음에는 좀 어렵게 생각해서, 강호가 받을 수 있는 최대 팁을 백트래킹을 이용해 풀어볼까 했지만,

 

스타박스 앞에 서 있는 사람의 수가 최대 10만이므로 백트래킹은 어렵다고 판단되었고 다른 방법을 찾아보게 되었다.

 

일단 문제의 난이도가 크게 높지 않고, 팁이 들어오는 계산식이 일정하게 변화하므로,

 

정렬을 통해 원래 주려고 했던 팁이 많은 손님 순서대로 정렬한 뒤,

 

계산값을 total 변수에 저장하는 식으로 진행했다.

 

여기서 효율성을 높이기 위해, 음수가 나오는 경우 그 뒤 팁들도 모두 음수가 나오므로 

 

바로 반복문을 멈추어 주었다.

 

import sys
 
n = int(sys.stdin.readline())
 
li = []
for i in range(n):
    li.append(int(sys.stdin.readline()))
 
li.sort(reverse=True)
 
total = 0
for i in range(n):
    ans = li[i] - i
    if ans < 0:
        break
    total += li[i] - i
 
print(total)

 

---

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

1758번: 알바생 강호