[백준] 11508번 : 2+1 세일 (파이썬)

그리디 알고리즘 문제

 

(1) 처음 내 코드 (성공)

n=int(input())
price=[]
cost=0
for _ in range(n):
    a=int(input())
    price.append(a)
price.sort(reverse=True)

if len(price)<3:
    for i in price:
        cost+=i
else:
    for i in range(len(price)):
        if ((i+1)%3==0):
            continue
        else:
            cost+=price[i]
print(cost)

처음에, 구매하려는 유제품 갯수가 3개 미만일 때와 그 이상일 때의 경우로 케이스를 나눴다.

 

(1) 유제품 갯수가 3개 미만일 때

그냥 모든 값을 더해주면 된다. 

 

(2) 유제품 갯수가 3개 이상일 때

우리는 최소 비용으로 2+1 유제품을 구매하려는 게 목적이다. 

예를 들어서 6개의 유제품을 구매하려고 할 때, 그 가격이 각각 6,5,4,3,2,1원이라면 우리는 (6,5,4),(4,3,2),(1) 이렇게 묶어주는게 가장 효율적이다. 즉, 유제품의 가격이 들어있는 리스트를 정렬 후에 2(3-1),5(6-1)번째 인덱스의 유제품만 전체 비용에서 제외시켜주면 되는 것이다.

 

위와 같은 풀이로 성공은 했지만, 시간을 보니 4052ms나 걸렸다. 내 생각에 for문 안에서 (index+1)%3을 매번 계산하는 코드가 시간을 많이 잡아먹은 것 같다. 따라서 이 부분을 최적화해서 다시 풀어보았다.

 

(2) 최적화 후 내 코드

import sys
input = sys.stdin.readline
n=int(input())

price = [int(input()) for _ in range((n))]
price.sort(reverse=True)
cost = sum(price)

for i in range(2,n,3):
    cost-=price[i]

print(cost)