[BOJ 1758번] 알바생 강호(Python)

📝 문제

💡 스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다.
스타박스에서는 손님을 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보다 작거나 같은 자연수이다.

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

 

문제링크

1758번: 알바생 강호

---

✅ 풀이

import sys
n = int(input())
cust = []
money1 = 0
money2 = 0
for i in range(n):
    cust.append(int(sys.stdin.readline()))
custwo = sorted(cust)
cust.sort(reverse=True)
idx = 1
for item in cust:
    tip = item-(idx-1)
    if tip <= 0:
        continue
    else:
        money1 += tip
        idx += 1

idx = 1
for item in custwo:
    tip = item-(idx-1)
    if tip <= 0:
        continue
    else:
        money2 += tip
        idx += 1
print(max(money1, money2))

💡 애매한 경우는 생각하지 않기 위해서 금액 크기순, 크기 역순으로 정렬해서 생각했다.
금액 크기순으로 정렬한 경우 큰 금액을 다 챙기지만 작은 금액을 놓치고,
크기 역순으로 정렬한 경우 놓치는 금액의 양을 최대한 줄이게 된다.

두 경우를 모두 구한 뒤, 더 큰 금액을 출력해주도록 했다.