11508번: 2+1 세일
KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두
www.acmicpc.net
문제
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개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 2^31-1보다 작거나 같다.
코드
import sys
input = sys.stdin.readline
n = int(input())
cost = []
for _ in range(n):
cost.append(int(input()))
cost.sort(reverse=True)
package = []
for i in range(0, n, 3):
package.append(cost[i:i+3])
ans = 0
for p in package:
if len(p) < 3:
ans += sum(p)
else:
ans += sum(p) - min(p)
print(ans)
꾸러미에서 무료로 구매할 수 있는 것들의 합을 최대로 해야 우리가 최소로 금액을 지불할 수 있다. 따라서 물건의 가격들을 내림차순으로 정렬하여 앞에서부터 3개씩 뽑으면 최소로 금액을 지불하도록 꾸러미를 만들 수 있다.
예를 들어, 물건 가격들이 [2, 1, 9, 4, 7, 3, 8]이라면 내림차순 정렬을 하면 [9, 8, 7, 4, 3, 2, 1]인데 앞에서부터 3개씩 묶어서 꾸러미를 만들면 [9, 8, 7], [4, 3, 2], [1]의 3개의 꾸러미가 나오게 된다. 앞의 2개의 꾸러미를 살펴보면 7과 2는 계산되지 않는다. 7은 2번째 꾸러미의 값들보다 크지만 1번째 꾸러미에서는 값이 가장 작아서 계산되지 않는다. 2 역시도 마찬가지이다. 즉, 내림차순으로 정렬하여 3개씩 묶어야 앞 꾸러미의 가장 작은 값이 뒷 꾸러미의 가장 큰 값보다 크지만 계산되지 않으므로 지불해야할 값을 최소로 할 수 있다.
import sys
input = sys.stdin.readline
n = int(input())
cost = []
for _ in range(n):
cost.append(int(input()))
cost.sort(reverse=True)
ans = 0
for i in range(0, n, 3):
if i < n - 1:
ans += cost[i] + cost[i + 1]
else: # 마지막에 물건이 1개만 남는 경우
ans += cost[i]
print(ans)
어차피 내림차순 정렬을 하여 큰 값 2개만 더하면 되니까 package 배열을 따로 쓰지 않고 바로 더해주어도 될 것 같아서 코드를 다음과 같이 수정하였다. 이해하기에는 위의 코드가 더 쉽지만 메모리와 시간 효율 측면에서는 아래의 코드가 더 효율적이다.
'문제풀이 > Greedy' 카테고리의 다른 글
[Python/파이썬] 백준 1541번 잃어버린 괄호 (0) | 2023.02.14 |
---|---|
[Python/파이썬] 백준 11047번 동전 0 (0) | 2023.02.08 |
[Python/파이썬] 백준 11399번 ATM (0) | 2023.02.08 |
[Python/파이썬] 백준 1758번 알바생 강호 (0) | 2023.02.07 |
[Python/파이썬] 백준 2217번 로프 (0) | 2023.02.07 |