[백준] 11508 2+1 세일

문제

• 유제품을 3개 한 번에 산다면 그 중 가장 싼 것은 무료로 받을 수 있다.
• N팩의 유제품을 구입하려고 할 때 최소 비용으로 유제품 구입하기

 

• 1 <= N <= 100,000
• 1 <= 유제품 가격 <= 100,000

 

풀이

• 3개 중 가장 싼 것은 무료로 받을 수 있으므로, 가격이 높은 제품을 무료로 받아야 최소 비용으로 구입할 수 있다.
• 전체 가격을 내림차순으로 정렬한 뒤 가격 순으로 3개씩 끊어서 구입한다.

 

N = int(input())
prices = [int(input()) for _ in range(N)]

prices.sort(reverse=True)
answer = sum(prices[::3]) + sum(prices[1::3])
print(answer)

 

References

• 백준 그리디