[백준] 11508 2+1 세일

문제

• 유제품 3개를 사면 그 중 싼 것은 무료고, 나머지 2개의 가격만 지불하면 된다.
• N개의 유제품을 구매하려고 할 때 최소비용은?
  • 1 <= N <= 100,000

 

풀이

• 정렬한 뒤 금액이 큰 순으로 3개씩 끊어서 비용 구하기

 

N = int(input())        # 유제품 수
prices = []             # 유제품 가격들
for _ in range(N):
    prices.append(int(input()))

prices.sort(reverse=True)   # 가격 순으로 정렬
answer = 0                  # 비용 (정답 변수)
# 3개씩 살펴보기
for i in range(0, N - (N%3), 3):
    answer += prices[i] + prices[i+1]
# 3개 묶음에 포함되지 않아 낱개로 사야하는 제품들 더하기
if N % 3 > 0:
    answer += prices[-1]
if N % 3 > 1:
    answer += prices[-2]

print(answer)

 

References

• 백준 11508번
• 2023.04.25 오늘의 문제