[Python] 백준 11508번_2+1 세일

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초
• 메모리 제한: 64 MB

 

"""
입출력 예시)

(예제 입력 1) 
4
3
2
3
2
    -> 8

(예제 입력 2)
6
6
4
5
5
5
5
    -> 21
"""

# 예제 1 : 재현이가 (3, 2, 2), (3)으로 총 2번에 걸쳐서 유제품을 사면 됨
# 예제 2 : 재현이가 (6, 4, 5), (5, 5, 5)로 총 2번에 걸쳐서 유제품을 사면 됨

 

 

 

첫 번째 시도

 

## 의사코드 ##

# 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불
# 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불

# 가격 리스트를 작은 값부터 오름차순 정렬
# 가격 리스트.sort()

# total = 0 # 비용

# while prices:
#     # 가격 리스트의 길이를 3으로 나눈 몫이 1이상인 경우
#     if (len(prices) // 3) >= 1:
#         min_price = prices.pop(0) # 3개 중 가장 싼 값
#         # total = total + 가격 리스트의 가장 왼쪽 가격 + 가격 리스트의 가장 오른쪽 가격
#         total += (prices.pop(0) + prices.pop()) 
#     # 가격 리스트의 길이를 3으로 나눈 몫이 1미만인 경우
#     else:
#         # total = total + 가격 리스트의 가장 왼쪽 가격
#         total += prices.pop(0)

 

n = int(input())
prices = []
for _ in range(n):
    price = int(input())
    prices.append(price)

# 가격 리스트를 오름차순 정렬
prices.sort()

total = 0 # 비용
while prices:
    # 가격 리스트의 길이를 3으로 나눈 몫이 1이상인 경우
    if (len(prices) // 3) >= 1:
        min_price = prices.pop(0) # 3개 중 가장 싼 값
        # total = total + 가격 리스트의 가장 왼쪽 가격 + 가격 리스트의 가장 오른쪽 가격
        total += (prices.pop(0) + prices.pop()) 
    # 가격 리스트의 길이를 3으로 나눈 몫이 1미만인 경우
    else:
        # total = total + 가격 리스트의 가장 왼쪽 가격
        total += prices.pop(0)
print(total)

-> 틀림

 

문제에서 설명된 예제 힌트를 보고 가격 리스트를 작은 값부터 오름차순 정렬해서 구하는 걸로 했더니 틀렸다.

 

 

• 과정 확인

"""
prices: [4, 5, 5, 5, 5, 6]
len(prices): 6 

min_price: 4
prices[0]: 5
prices[-1]: 6
total: 11
--------------------------------------------------
prices: [5, 5, 5]
len(prices): 3 

min_price: 5
prices[0]: 5
prices[-1]: 5
total: 21
--------------------------------------------------
"""

 

 

 

통과한 코드

 

## 의사코드 ##

# 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불
# -> 최소비용이 되려면 무료로 지불할 가장 싼 것이 최대한 비싼 물건이 되도록 해야 함
# 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불

# 가격 리스트를 큰 값부터 내림차순 정렬
# 가격 리스트.sort(reverse=True)

# min_prices = 0 # 무료로 지불할 가장 싼 가격들의 합

# # 내림차순으로 정렬된 가격 리스트에서 3의 배수 번째 가격을 더함 
# for i in range(2, n, 3): # n = len(prices)
#     min_prices += prices[i]

# # 최소 비용 = 전체 가격의 합 - 무료로 지불할 가장 싼 가격들의 합
# sum(prices) - min_prices

 

n = int(input())
prices = []
for _ in range(n):
    prices.append(int(input()))

# 가격 리스트를 내림차순 정렬
prices.sort(reverse=True)

# 무료로 지불할 가장 싼 가격들의 합
min_prices = 0 

# 내림차순으로 정렬된 가격 리스트에서 3의 배수 번째 가격을 더함 
for i in range(2, n, 3): # n = len(prices)
    min_prices += prices[i]

# 최소 비용 = 전체 가격의 합 - 무료로 지불할 가장 싼 가격들의 합
print(sum(prices) - min_prices)

-> 가격 리스트를 큰 값부터 내림차순 정렬하면 3의 배수 번째 가격들이 무료로 지불할 가장 싼 가격들이 됨

(최소 비용이 되려면 무료로 지불할 가장 싼 가격들이 최대한 비싼 금액이 되어야 하기 때문)

 

이 무료로 지불할 가장 싼 가격들의 합을 구해서 전체 가격의 합에서 빼준 값이 최소 비용

 

• cf) 'for i in range(2, n, 3)' 에서 n 대신 len(prices)를 사용하면 시간 초과 뜸
• 과정 확인

prices = [6, 5, 5, 5, 5, 4]

"""
i: 2
prices[i]: 5
min_prices: 5 

i: 5
prices[i]: 4
min_prices: 9 

21
"""

 

 

 

 

 

참고)

 

https://velog.io/@bye9/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-11508-21-%EC%84%B8%EC%9D%BC

[백준/파이썬] 11508 2+1 세일