[백준 11508] 2+1 세일 - 그리디 알고리즘

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

 

문제

•  유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불
• 재현이가 N개의 유제품을 모두 살 때 필요한 최소비용 출력

 

접근

일단, 3개당 하나의 물건의 가격이 무료가 된다. 그러면 무료가 가능한 갯수는 N/3개

그렇다면 해당 물건의 가격이 최대가 되게 하면 된다.

 

1. 물건의 가격을 내림차순으로 정렬

2. 3등부터 상위 3개 선정

 

근데 문제가 있다. 1,2,3등을 고르면 자연스레 그 다음 최대는 4,5,6등이 된다. 이렇게 잘라서 무료가 되게 하면 이것이 왜 최선인가???

비슷한 것끼리 묶어야지 무료 금액이 커진다. 어자피 더 적은 금액을 선택해보더라도 더 작은 값이 최소 금액이 되므로 무료 금액 최대화가 안된다.

 

N = int(input())
items= []
for i in range(N):
    items.append(int(input()))
    
   
items.sort(reverse=True)
sum = 0
for idx in range(len(items)):
    if (idx+1)%3 == 0:
        pass
    else:
        sum +=items[idx]
        
print(sum)

 

주요 문법 및 주의사항

input()은 문자열을 반환하므로 형변환 필요

3의 배수가 나머지가 0인 것을 이용해서 3번째, 6번째 항목을 무료로 하려고 했다.

그러나 인덱스는 0부터 시작 그래서 +1을 해주어야 했다.