[백준] #11508 2+1 세일 (python)

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

11508번: 2+1 세일

 

문제

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

예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을, 두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다.

재현이는 KSG 편의점에서 친구들과 같이 먹을 총 N팩의 유제품을 구입하려고 합니다. 재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

입력

첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.

두 번째 줄부터 N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어집니다.

출력

재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 231-1보다 작거나 같다.

 

예제 입력1

4
3
2
3
2

예제 출력1

8

 

예제 입력2

6
6
4
5
5
5
5

예제 출력2

21

 

---

# Code

n = int(input())
price = []

for i in range(n):
    price.append(int(input()))

price.sort(reverse=True)

sum = 0
for i in range(len(price)):
    if i%3==0 or i%3==1:
        sum+=price[i]

print(sum)

# Comment

아니.. 이거 알바생 강호 문제랑 푸는 방법 비슷한 것 같아서 그렇게 하면 되겠군 생각했는데 처음에 문제에서

"예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을, 두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다."

이부분을 이게 답이라는 걸로 착각해서 ㅋㅋㅋㅋㅋㅋ 아니 얘는 .. 왜.. 이게 답이지? 어떻게 푸는거지 이거 아닌가? 하면서 헷갈려하다가 결국 내가 생각한 풀이가 맞다는걸 깨달았다.. ㅋㅋㅋㅋ 

 

무료로 받을 수 있는 물건의 값이 클 수록 좋으니까, 문제 예시를 이용해서 설명해보자면

10 9 4 2 6 4 3 -> 10 9 6 4 4 3 2 -> (10, 9, 6) (4, 4, 3) (2) -> 19 + 8 + 2 = 29 

이렇게 물건의 값이 높은 것부터 내림차순 정렬을 해준 다음 앞에서부터 세개씩 묶는다. 

index는 0부터 시작되므로, 마지막 물건을 빼고 더하려면 index 값을 3으로 나눈 나머지가 0 또는 1 인 것들만 sum 에 더해주면 된다. 마지막에 홀로 묶여있는 (2) 같은 경우 index가 6이므로 3으로 나눈 나머지가 0이기 때문에 sum에 더해진다.