[Python] 1758번 알바생 강호

✏️ 문제

 

문제 파악

꾸러미 중에 제일 작은 가격이 공짜이므로 큰 금액을 공짜로 받으면 이득이므로 꾸러미에 제일 작은 가격과 그 가격과 별로 차이 나지 않는 가격들끼리 묶어놓는 게 좋다.

 

그래서 정렬을 사용한 후 3의 배수 번째의 위치에 있는 가격들이 공짜이므로 그 가격들 제외하고 더하는 방식으로 풀었다.

 

알고리즘

• 그리디 알고리즘
• 정렬

 

 

코드

n = int(input())
line = []
tip = 0

for i in range(n):
  line.append(int(input()))

line.sort(reverse=True)

for i in range(n):
  if line[i]-(i+1-1) > 0:
    tip += line[i]-(i+1-1)

print(tip)