[solved.ac 실버4] 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보다 작거나 같다.

예제

---

나의 풀이

가장 싸게 사기 위해서는 비싼 제품을 공짜로 받아야 한다.

어떤 유제품을 공짜로 받기 위해서는 그 유제품보다 비싼 유제품을 2개 같이 사야한다.

할인 받을 수 있는 가장 비싼 유제품은 사려고 하는 유제품 중 3번째로 비싼 유제품일 것이다. 그리고 3번째로 비싼 유제품을 사기 위해서는 가장 비싼 유제품 2개를 함께 구매해야 한다.

이렇게 3개의 유제품을 사고, 남은 유제품 중에서 또 가장 싸게 사기 위해서는 남은 유제품 중 3번째로 비싼 유제품을 공짜로 받는 것이다.

이런 과정을 반복하게 되면 가장 싸게 살 수 있는 경우를 찾을 수 있다.

 

1. 사고자 하는 유제품들을 입력 받는다.
2. 내림차순으로 정렬한다
3. 3번째 마다 제거한다. (혹은 가격을 0으로 만든다)
4. 남아 있는 유제품들의 가격을 모두 더한다
5. 4번에서 구한 값이 답이 된다.

 

쉬운 버전

n = int(input())
items = [] # 유제품 리스트
for _ in range(n): # n 번 반복
    item = int(input())
    items.append(item) # 유제품 리스트에 추가
items.sort(reverse=True) # 내림차순으로 정렬

for i in range(n):
    if not (i + 1) % 3: # 3으로 나눈 나머지가 0
        items[i] = 0 # 3개 마다 가격을 0으로 만듦

answer = sum(items) # 사야 하는 유제품의 합
print(answer)

쉬운 문제인 만큼 기본적인 파이썬 문법만을 사용한 풀이도 만들어 보았다.

이 풀이는 3개 마다 가격을 0으로 만드는 방법을 사용했다.

 

짧은 버전

print(sum([x for i, x in enumerate(sorted([int(input()) for _ in range(int(input()))], reverse=True)) if (i + 1) % 3]))

한 줄로 풀 수 있다.

이 풀이는 3개 마다 리스트에서 제외하는 (정확히는 3번째가 아닌 아이템만 리스트에 담는) 방법을 사용했다.

 

채점 결과

코드 길이가 119B인 것이 한 줄로 푼 버전이고, 354B인 것이 쉬운 버전이다. 메모리나 시간에서는 유의미한 차이는 없다.

만약 시간을 좀 더 줄이고 싶다면 (쉬운 버전에서) 3번째 마다 0으로 만드는 것이 아니라 3번째인 것을 제외하고, 바로 합을 더해 나가는 방법도 있겠다. (sum 함수를 사용하면 한 번 더 리스트를 탐색해야 하므로 중복으로 탐색하는 만큼 시간이 좀 더 소요되기 때문)