[Python] 백준 #11508- 2+1 세일

문제

11508번: 2+1 세일

---

코드

---

My answer

import sys
input = sys.stdin.readline

n=int(input())
price=[int(input()) for i in range(n)]
price.sort(reverse=True)
answer=[]
result=0

for i in range(0,n-2,3):
    answer.append(price[i:i+3])
answer.append(price[i+3:])

for i in answer:
    if(len(i)==3):
        result+=sum(i)-min(i)
    else:
        result+=sum(i)
print(result)

Another answer

from sys import stdin
n=int(input())
m=list(map(int, stdin.read().split()))
m.sort(reverse=True)
cost = 0
for i in range(n):
    if(i%3!=2):
        cost += m[i]
print(cost)

풀이

---

그리디 문제로, 최소가격을 내기 위해서는 무료로 받는 상품의 가격이 커야한다. 

단 무료로 받는 상품은 선택한 3개 중 가장 싼 것이기 때문에 단순하게 큰놈들끼리 묶으면 해결되는 문제다.

내 풀이: 3개씩 묶은 리스트를 만들고, 각 리스트에서 젤 작은 것을 제외하고 합침

다른 풀이: 정려한 후, 3으로 나눠서 나머지가 2인 인덱스들만 제외하고 더함

 

똑같은 아이디어지만, 두번째 방식이 새로운 리스트도 안만들고, 연산도 적게하므로 메모리도 적게들고, 빠르다.