[백준 11508번] 2+1 세일

문제 링크 >> https://www.acmicpc.net/problem/11508

 

 

📋 문제

KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다.

KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다.

한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다.

 

예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을, 두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다.

 

재현이는 KSG 편의점에서 친구들과 같이 먹을 총 N팩의 유제품을 구입하려고 합니다.

재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

 

 

👉 입력

첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.

두 번째 줄부터 N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어집니다.

 

 

👈출력

재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다.

정답은 231-1보다 작거나 같다.

 

 

📝 풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]
arr.sort(reverse=True)
result = 0

for i in range(0, n, 3):
  item = arr[i:i+3]
  if len(item) == 3:
    total = sum(item) - min(item)
    result += total
  else:
    for j in item:
      result += j
      
print(result)

 

n은 입력으로 주어진 유제품 수이며 arr은 각 유제품의 가격이 저장되어 있는 리스트입니다.

먼저 유제품을 구매하는 비용을 최소로 하기 위해 arr을 내림차순으로 정렬합니다.

내림차순으로 정렬하는 이유는 3개 중 하나는 무료이기 때문에 최대한 비싼 것을 무료로 지불하기 위해서 입니다.

 

이후 for문을 돌며 가격의 합을 구합니다.

2+1 세일에 해당할 경우 3개 중 가장 싼 것은 제외하고 가격의 총 합을 구합니다.

2+1 세일에 해당하지 않을 경우 item의 요소들을 모두 지불할 가격에 더합니다.