<그리디> 백준 11508번. 2+1세일 (실버 4)

https://www.acmicpc.net/problem/11508

11508번: 2+1 세일

1차 시도 :

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
cost = []
total = 0
for _ in range(n):
  cost.append(int(input()))

# 2 3 4 4 6 9 10
# 10 9 6 4 4 3 2
while cost :
  cost.sort(reverse=True)
  if len(cost) < 3:
    total += sum(cost)
    break
  total += cost.pop(0)
  cost.pop()
  total += cost.pop()

print(total)

"""
7
10
9
6
4
4
3
2

"""

시간 초과가 떴다. 반복문 안에서 계속해서 sort해줘서 그런 것 같다..  

다시 보니깐 잘못된 코드인 듯. 문제에 적힌 예시를 읽고 더 헷갈렸다. 문제에선 10,9,6,4,4,3,2를  (10, 3, 2), (4, 6, 4), (9)로 묶어 13+10+9=32원을 지불하는 것으로 적혀 있어서 이렇게 묶이도록 구현하였는데,

다시 생각해보니 3개의 제품 중 가장 싼 제품이 무료이므로 이 3번째 제품이 최대한 비싸야한다.

그럼 (10,9,6) (4,4,3) (2) =>19+8+2 = 29원으로 이 방법이 더 최소비용이다.

 

뭐지.. 문제가 잘못됐을 확률보다 내 생각이 틀렸을 확률이 더 클거 같은데 의문이다...

 

무튼 다시 생각한 방식대로 코드를 작성해주었는데,

import sys
input = sys.stdin.readline

n = int(input())
cost = []
# 10 9 4 4 6 3 2
for _ in range(n):
  cost.append(int(input()))

total = sum(cost)

cost.sort(reverse=True)
2
for i in range(n):
  if i %3==2: #인덱스는 0부터 시작하므로 나머지 2가 3,6,9..번째를 뜻함
    total -= cost[i]  
   
  
  
print(total)  
"""
7
10
9
6
4
4
3
2

"""

정답이다!

문제 예시를 넣어봤는데, 29원 나온다!