[백준/그리디 알고리즘] 알바생 강호

문제

 

스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다.

스타박스에서는 손님을 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보다 작거나 같은 자연수이다.

 

출력

 

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

 

문제 해설

 

"이 문제의 핵심은 팁을 받을 순서를 큰 순서대로 리스트에 배열하는 것이다"

 

만약 예를 들어 1 1 9 9 가 주어진다고 한다면, 작은숫자 즉 1이 뒤로가게 된다면

돈 - (받은 등수 - 1) 의 값이 음수가 나오게 된다. 따라서 1은 두번째부터 0의 값이 나오게 되므로 어디서 줄을서도 어차피 팁은 0원이 된다.

하지만 큰 숫자들은 뒤로 갈수록 원래 주려고 했던 팁이 줄어들게 된다. (등수가 낮을수록 원래 주려했던 팁에서 큰수를 빼야 하기 떄문에)

즉 그리디 알고리즘의 핵심인 팁을 최대로 받을수 있는 최적의 방법에서 멀어지기 떄문에 이를 해결하기 위해서는 내림차순으로 정렬하여

입력받는 고객의 팁을 역순으로 정렬하여 풀어야 한다.

 

# 풀이 1

n = int(input()) #사람의 수 N이 주어짐
tip = [] #tip을 넣을 리스트 생성
for _ in range(n):
    a = int(input())
    tip.append(a) 
tip.sort(reverse = True) #줄 (선사람의 생각하는 팁을 받아와 큰 순서대로 배열

rate = 1 #등수 초기화
result = 0 #결과값 초기화
for i in tip:
    if (i - (rate-1)) >= 0: #(주려고생각한 팁 - (받은등수 - 1)) 이 음수가 아닌 경우만 알고리즘 생성
        result = result + (i - (rate-1))ㅌ 
        rate += 1
    else:
        continue
print(result)

# 풀이 2

import sys
input = sys.stdin.readline()
n = int(input())
arr = [int(input() for _ in range(n))]

arr.sort(reverse = True)
sum = 0

for i in range(n):
    if arr[i] - i < 0:
      continue
    sum += (arr[i] - i)

print(sum)

# 강호가 최대의 팁을 얻어야 하므로 입력받는 고객의 팁을 역순으로 정렬해서 풀면 된다. 
# 또한 이후 강호가 받게 되는 팁이 음수가 된다면 아무것도 받지 않는 부분만 코드에 추가해 주면 된다.