[BOJ 11508, Python 3] 2+1 세일

알고리즘/BOJ

70825 2021. 8. 3. 15:49

11508번: 2+1 세일

KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두

www.acmicpc.net

최솟값을 지불하는 방법을 도출하라고 합니다.

이 말을 살짝 비틀어서 무료로 받을 수 있는 상품의 금액을 최대화한다고 생각해봅시다.

무료로 받는 상품의 금액을 최대화해야하니 최대한 큰 값을 무료로 받으면 좋은 것은 당연합니다.

그러면 내림차순으로 정렬해봅시다.

첫번째 값과 두번째 값은 무조건 사야하고, 세번째로 비싼 상품은 무료로 받을 수 있습니다.

이렇게 1+2, 3무료, 4+5, 6무료, ... 이런 방식으로 사는 것이 최적해인 것을 알 수 있습니다.

1
2
3

n = int(input())
arr = sorted([int(input()) for i in range(n)])[::-1]
print(sum(arr[i] for i in range(n) if i % 3 < 2))

cs