[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보다 작거나 같다.

 

[예제]

 

[풀이]

 풀이에서 가장 중요한 포인트는 최소 비용을 구하는 과정은 더하기로 수행된다는 것이다. 만약 곱해서 더했을 때의 최소값을 구한다면 최대한 작은 수들 간의 곱을 구하고 더해야겠지만, 그냥 더해서 최소비용을 구하는 문제라는 점을 고려해봐야 한다. 그러면, 최대한 비싼 유제품의 비용을 지불하지 않도록 하는게 포인트라고 할 수 있다.

 이 과정을 수행하기 위해서는 유제품의 가격을 내림차순으로 정렬하고, 큰것부터 순서대로 3개씩 묶어주면 된다. 만약, 유제품 가격의 리스트가 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 이라고 하면 아래와 같이 풀이할 수 있다.

[10, 9, 8] : 8 제외 & 19 지불

[7, 6, 5] : 5 제외 & 13 지불

...

 

💡 풀이 1번 : 정렬 > 큰 것부터 3개씩 묶어 앞에 두개만 더하기

import sys
input = sys.stdin.readline

n = int(input())
lst = [int(input()) for _ in range(n)]
lst.sort(reverse = True)
answer = 0

for i in range(0, n, 3):
  if n - i <= 2:
    answer += sum(lst[i:])
    break;
  answer += sum(lst[i : i + 2])

print(answer)

 

💡 풀이 2번 : 정렬 > (전체 합) - (큰 것부터 3개씩 묶어 맨 마지막 값들의 합)

import sys
input = sys.stdin.readline

n = int(input())
lst = [int(input()) for _ in range(n)]
lst.sort(reverse = True)
answer = 0

for i in range(2, n, 3):
  answer += lst[i]

print(sum(lst) - answer)

 풀이 1번을 반대로 생각해본게 풀이 2번인데, 이렇게 반대로도 생각해볼 수 있도록 노력해야겠다 !