문제
재관이의 옷 매장에서 대량 세일을 하고자 한다.
세일에는 조건이 한가지 있는데, 세 벌의 옷을 사면 그 중 가장 저렴한 한 벌에 해당하는 값은 내지 않아도 된다는 조건이다.
그리고 세 벌보다 많은 옷을 구매하는 경우에도 옷을 세 벌씩 나눠서 계산하면 같은 방식의 할인을 받을 수 있다.
예를 들면 10, 3, 2, 4, 6, 4, 9원짜리 옷을 사고자 할 때 (3, 2, 4), (10, 4, 9), (6)원짜리로 묶어서 계산을 하게 된다면,
첫 묶음에서 2원, 두 번째 묶음에서 4원 총 6원의 할인을 받게 되는 것이다.
다만 세 번째 묶음은 한 벌만 구매하므로 할인이 적용되지 않는다.
재관이네 매장에서 사고자 하는 옷이 있을 때 어떻게 묶어서 결제를 하면 가장 할인을 많이 받아서 구매를 할 수 있는지 계산하여라.
두 번째 테스트케이스를 예로 보면, {6,4,5,5,5,5}의 옷들이 있을 때 (6,4,5), (5,5,5)로 묶으면 가장 저렴한 조합이 된다.
[입력]
맨 위 줄에 테스트케이스의 개수가 주어진다.
각 테스트케이스 별로 순서대로 첫째 줄에 사고자 하는 옷의 벌 수 N (1 ≤ N ≤ 100,000)이 주어진다.
다음 줄에는 N개의 옷의 가격 Ci (1 ≤ Ci ≤ 100,000)가 띄어쓰기로 구분되어 주어진다.
[출력]
각 테스트케이스 별로 순서대로 한 줄씩 답을 출력하는데, 지불해야 할 최소의 금액을 출력한다.풀이
3개의 옷묶음이 있을경우, 그중 가장 작은가격의 옷은 공짜다
만약, {5,5,6}처럼 작은가격의 옷이 2개일경우, 1개를 공짜로 친다.
즉, 3개의 옷묶음이 있을 경우, 이 묶음에서 가장작은 가격은 최대한 높아야 한다.
- list를 내림차순으로 정렬 후, 3개씩 묶는다.
- 3번째마다 가격을 매기지 않으므로 pass
res=[]
for m in range(int(input())):
tmp=0
idx=0
N=int(input())
li=sorted(list(map(int,input().split())),reverse=True)
for i in range(len(li)):
if idx!=2:
tmp+=li[i]
idx+=1
else:
idx=0
res.append(tmp)
for i in range(len(res)):
print("#%d %s"%(i+1,res[i]))
뉴비