[BOJ][Python] 11508번 - 2+1 세일[정렬- 실버 4티어]

알고리즘 태그

[정렬]

태그 설명

정렬이란 데이터의 집합을 어떠한 기준의 대소관계를 따져 일정한 순서로 줄지어 세우는것

문제

백준 문제 - 2+1 세일

링크: 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팩의 유제품을 구입하려고 합니다. 재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

예제 입력 1 

4
3
2
3
2

예제 출력 1 

8

예제 입력 2 

6
6
4
5
5
5
5

예제 출력 2 

21​

 

단순하게 비싼것들만 먼저 묶고, 비싼것들 중에서 가장 저렴한것을 무료로 받으면 간단하게 풀 수 있다.

왜? Why? 가장 저렴한 값을 구하려면 일단 비싼 물건들을 먼저 제거해야한다고 판단했다.

즉, 2번 예제로 따지면 [6,5,5] [5,5,4] 이런식으로 2개의 리스트로 나눠서 처리하면 된다.

이 문제에서 핵심은 어떻게 내가 원하는 숫자로 리스트를 잘라낼것인가가 문제였던거 같다.

import sys
n = int(input())
numbers = []
for _ in range(n):
     numbers.append(int(sys.stdin.readline()))  
     
sorted_number = sorted(numbers,reverse=True)

start_pos = 0
end_pos = len(numbers)
divide = 3

result = 0

for index in range(start_pos,end_pos,divide):
  # [0:3] -> [3:6] 이런식으로 잘라내는 알고리즘!
  product = sorted_number[start_pos:start_pos+divide]
  
  start_pos = start_pos + divide
  # 잘라낸 리스트의 갯수가 3개면?
  if len(product) == 3:
    # 가장 마지막(정렬을 했으니 가장 마지막은 해당 리스트에서 가장 싼 제품이다.)을 더해서 누적
    result+=sum(product[:2])
  else:
    # 3개가 안된다면 어차피 다 더해야한다.
    result+=sum(product)
    
print(result)

 

다른 예시 코드도 공부해봤다.

from sys import stdin
n=int(input())
m=list(map(int, stdin.read().split()))
# 내림차순으로 정렬
m.sort(reverse=True)
cost = 0

for i in range(n):
	# 내림차순으로 정렬을 해놨으니, 3번째로 들어오게 되는 값만 제외시키면 정답이 된다.
    # ex) cost += m[0],m[1],m[3],m[4],m[6],m[7]...
    # 훨씬 간결한거같다...
    if(i%3!=2):
        cost += m[i]
print(cost)

수학적으로 잘푼거같다!