COCI 2015/2016 contest1 2- 2+1 세일(AKCIJA) > 문제은행 : 정보올림피아드&알고리즘




2977 : 2+1 세일(AKCIJA)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
56 회   
시도횟수
111 회   

문제

KOI 서점에서는 개업 32주년을 맞아 2권의 책을 사면 1권을 공짜로 주는 '2+1 세일'하는 행사를 하고 있다. 

KOI 서점은 고객이 구입할 책 3권을 가져 오면 가장 싼 책을 제외하고 나머지 두권의 가격만 받는 형태로 '2+1 세일'을 진행한다. 

단, 3권보다 적은 개수를 구매하는 경우에는 세일이 적용되지 않는다.

 

예를 들어, 7권의 책이 있고 각 가격이 10, 9, 4, 2, 6, 4, 3이고 동현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 

첫 번째 꾸러미에서는 13달러, 두 번째 꾸러미에서는 10달러, 세 번째 꾸러미에서는 9달러이므로 총 32달러 지불하면 된다. 

또한 다른 방법으로 (10, 9, 6), (4, 3, 4), (2)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 19달러, 

두 번째 꾸러미에서는 8달러, 세 번째 꾸러미에서는 2달러이므로 총 29달러 지불하면 된다.

 

동현이는 KOI 서점에서 N권의 책을 구입하려고 한다. 동현이가 지불할 최소 금액은 얼마일까?

 


입력형식

첫 번째 줄에는 구입할 책의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄부터 N개의 줄에는 각 책의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어진다.

출력형식

동현이가 N권의 책을 모두 살 때 필요한 최소비용을 출력한다.

입력 예

4
3
2
3
2

출력 예

8

입력 예

6
6
4
5
5
5
5

출력 예

21


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP