백준 온라인 저지, 그리디 / 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개의 줄에는 각 유제품의 가격 C_i (1 ≤ C_i ≤ 100,000)가 주어집니다.

출력

재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 2³¹-1보다 작거나 같다.

제한

예제 입력 1

4
3
2
3
2

예제 출력 1

8

예제 입력 2

6
6
4
5
5
5
5

예제 출력 2

21

힌트

예제 1 : 재현이가 (3, 2, 2), (3)으로 총 2번에 걸쳐서 유제품을 사면 됩니다.

예제 2 : 재현이가 (6, 4, 5), (5, 5, 5)로 총 2번에 걸쳐서 유제품을 사면 됩니다.

W3sicHJvYmxlbV9pZCI6IjExNTA4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiMisxIFx1YzEzOFx1Yzc3YyIsImRlc2NyaXB0aW9uIjoiPHA+S1NHIFx1ZDNiOFx1Yzc1OFx1YzgxMFx1YzVkMFx1YzExY1x1YjI5NCBcdWFjZmNcdWM3N2NcdWM2YjBcdWM3MjAsIFx1YjRkY1x1YjljMVx1ZDBiOVx1YzY5NFx1YWQ2Y1x1Yjk3NFx1ZDJiOCBcdWI0ZjFcdWM3NTggXHVjNzIwXHVjODFjXHVkNDg4XHVjNzQ0ICYjMzk7MisxIFx1YzEzOFx1Yzc3YyYjMzk7XHVkNTU4XHViMjk0IFx1ZDU4OVx1YzBhY1x1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBLU0cgXHVkM2I4XHVjNzU4XHVjODEwXHVjNWQwXHVjMTFjIFx1YzcyMFx1YzgxY1x1ZDQ4OCAzXHVhYzFjXHViOTdjIFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVjMGIwXHViMmU0XHViYTc0IFx1YWRmOFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjMmZjIFx1YWM4M1x1Yzc0MCBcdWJiMzRcdWI4Y2NcdWI4NWMgXHVjOWMwXHViZDg4XHVkNTU4XHVhY2UwIFx1YjA5OFx1YmEzOFx1YzljMCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxY1x1ZDQ4OCBcdWFjMDBcdWFjYTlcdWI5Y2MgXHVjOWMwXHViZDg4XHVkNTU4XHViYTc0IFx1YjQyOVx1YjJjOFx1YjJlNC4gXHVkNTVjIFx1YmM4OFx1YzVkMCAzXHVhYzFjXHVjNzU4IFx1YzcyMFx1YzgxY1x1ZDQ4OFx1Yzc0NCBcdWMwYWNcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IFx1ZDU2MFx1Yzc3OCBcdWM1YzZcdWM3NzQgXHVjODE1XHVhYzAwXHViOTdjIFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3YyBcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDdcdWFjMWNcdWM3NTggXHVjNzIwXHVjODFjXHVkNDg4XHVjNzc0IFx1Yzc4OFx1YzViNFx1YzExYyBcdWFjMDEgXHVjODFjXHVkNDg4XHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc3NCAxMCwgOSwgNCwgMiwgNiwgNCwgM1x1Yzc3NFx1YWNlMCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWFjMDAgKDEwLCAzLCAyKSwgKDQsIDYsIDQpLCAoOSlcdWI4NWMgXHVjZDFkIDNcdWJjODhcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YmIzY1x1YWM3NFx1Yzc0NCBcdWMwYjBcdWIyZTRcdWJhNzQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFmYjhcdWI3ZWNcdWJiZjhcdWM1ZDBcdWMxMWNcdWIyOTQgMTNcdWM2ZDBcdWM3NDQsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVhZmI4XHViN2VjXHViYmY4XHVjNWQwXHVjMTFjXHViMjk0IDEwXHVjNmQwXHVjNzQ0LCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YWZiOFx1YjdlY1x1YmJmOFx1YzVkMFx1YzExY1x1YjI5NCA5XHVjNmQwXHVjNzQ0IFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3YyBcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBLU0cgXHVkM2I4XHVjNzU4XHVjODEwXHVjNWQwXHVjMTFjIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YWNmYyBcdWFjMTlcdWM3NzQgXHViYTM5XHVjNzQ0IFx1Y2QxZCBOXHVkMzI5XHVjNzU4IFx1YzcyMFx1YzgxY1x1ZDQ4OFx1Yzc0NCBcdWFkNmNcdWM3ODVcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTY5XHViMmM4XHViMmU0LiBcdWM3YWNcdWQ2MDRcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1Y2Q1Y1x1YzE4Y1x1YmU0NFx1YzZhOVx1YzczY1x1Yjg1YyBcdWM3MjBcdWM4MWNcdWQ0ODhcdWM3NDQgXHVhZDZjXHVjNzg1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViM2M0XHVjNjQwXHVjOGZjXHVjMTM4XHVjNjk0ITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzIwXHVjODFjXHVkNDg4XHVjNzU4IFx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzcyMFx1YzgxY1x1ZDQ4OFx1Yzc1OCBcdWFjMDBcdWFjYTkgQzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3YWNcdWQ2MDRcdWM3NzRcdWFjMDAgTlx1YWMxY1x1Yzc1OCBcdWM3MjBcdWM4MWNcdWQ0ODhcdWM3NDQgXHViYWE4XHViNDUwIFx1YzBiNCBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4Y1x1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc0MCAyPHN1cD4zMTxcL3N1cD4tMVx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWMgMSA6IFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YWMwMCAoMywgMiwgMiksICgzKVx1YzczY1x1Yjg1YyBcdWNkMWQgMlx1YmM4OFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHVjNzIwXHVjODFjXHVkNDg4XHVjNzQ0IFx1YzBhY1x1YmE3NCBcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzgxYyAyIDogXHVjN2FjXHVkNjA0XHVjNzc0XHVhYzAwICg2LCA0LCA1KSwgKDUsIDUsIDUpXHViODVjIFx1Y2QxZCAyXHViYzg4XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWM3MjBcdWM4MWNcdWQ0ODhcdWM3NDQgXHVjMGFjXHViYTc0IFx1YjQyOVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjExNTA4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQUtDSUpBIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIHByb21vdGlvbmFsIG9mZmVyIGluIGEgYm9va3N0b3JlICZsZHF1bztUYWtlIDMsIHBheSBmb3IgdGhlIDIgbW9yZSBleHBlbnNpdmUgb25lcyZyZHF1bzsuIFNvLCBlYWNoIGN1c3RvbWVyIHdobyBwaWNrcyAzIGJvb2tzIGdldHMgdGhlIGNoZWFwZXN0IG9uZSBmb3IgZnJlZS4gT2YgY291cnNlLCB0aGUgY3VzdG9tZXIgY2FuIHRha2UgZXZlbiBtb3JlIGJvb2tzIGFuZCwgZGVwZW5kaW5nIG9uIHRoZSB3YXkgdGhlIGJvb2tzIGFyZSBhcnJhbmdlZCBpbnRvIGdyb3VwcyBvZiB0aHJlZSwgZ2V0IHRoZSBjaGVhcGVzdCBvbmUgaW4gZWFjaCBncm91cCBmb3IgZnJlZS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGxldCB0aGUgcHJpY2VzIG9mIHRoZSBib29rcyB0YWtlbiBieSB0aGUgY3VzdG9tZXIgYmU6IDEwIDMgMiA0IDYgNCA5LiBJZiBoZSBhcnJhbmdlcyB0aGVtIGludG8gZ3JvdXBzOiAoMTAsIDMsIDIpLCAoNCwgNiwgNCkgYW5kICg5KSwgaGUgd2lsbCBnZXQgdGhlIGJvb2tzIHByaWNlZCAyIGZyb20gdGhlIGZpcnN0IGdyb3VwIGZvciBmcmVlIGFuZCB0aGUgYm9vayBwcmljZWQgNCBmcm9tIHRoZSBzZWNvbmQgZ3JvdXAuIFdlIGNhbiBzZWUgdGhhdCBoZSB3b24mcnNxdW87dCBnZXQgYW55dGhpbmcgZm9yIGZyZWUgZnJvbSB0aGUgdGhpcmQgZ3JvdXAgYmVjYXVzZSBpdCBjb250YWlucyBvbmx5IG9uZSBib29rLjxcL3A+XHJcblxyXG48cD5UaGUgbGFkeSB3b3JraW5nIGluIHRoZSBib29rc3RvcmUgaXMgd2VsbC1pbnRlbnRpb25lZCBhbmQgc2hlIGFsd2F5cyB3YW50cyB0byBsb3dlciB0aGUgcHJpY2UgZm9yIGVhY2ggY3VzdG9tZXIgYXMgbXVjaCBhcyBwb3NzaWJsZS4gRm9yIGdpdmVuIGJvb2sgcHJpY2VzLCBoZWxwIHRoZSBsYWR5IGFycmFuZ2UgdGhlIGJvb2tzIGludG8gZ3JvdXBzIGluIHRoZSBiZXN0IHdheSBwb3NzaWJsZSwgc28gdGhhdCB0aGUgdG90YWwgcHJpY2UgdGhlIGN1c3RvbWVyIGhhcyB0byBwYXkgaXMgbWluaW1hbC48XC9wPlxyXG5cclxuPHA+UGxlYXNlIG5vdGU6IFRoZSBsYWR5IGRvZXNuJnJzcXVvO3QgaGF2ZSB0byBhcnJhbmdlIHRoZSBib29rcyBpbnRvIGdyb3VwcyBzbyB0aGF0IGVhY2ggZ3JvdXAgY29udGFpbnMgZXhhY3RseSAzIGJvb2tzLCBidXQgdGhlIG51bWJlciBvZiBib29rcyBpbiBhIGdyb3VwIG5lZWRzIHRvIGJlIGJldHdlZW4gMSBhbmQgMywgaW5jbHVzaXZlbHkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGJvb2tzIHRoZSBjdXN0b21lciBib3VnaHQuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgQzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCAwMDApLCB0aGUgcHJpY2Ugb2YgZWFjaCBib29rLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG1pbmltYWwgcHJpY2UuPFwvcD5cclxuIiwiaGludCI6IjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIGZpcnN0IGV4YW1wbGU6IFRoZSBsYWR5IGNhbiBwdXQgdGhlIGJvb2tzIHByaWNlZCAzLCAyLCAyIGluIG9uZSBncm91cCwgYW5kIG9ubHkgdGhlIGJvb2sgcHJpY2VkIDMgaW4gdGhlIG90aGVyIGdyb3VwLCB3aGljaCBpcyBhbHNvIHRoZSBjaGVhcGVzdCBjb21iaW5hdGlvbi48XC9wPlxyXG5cclxuPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgc2Vjb25kIGV4YW1wbGU6IFRoZSBsYWR5IHB1dHMgYm9va3MgcHJpY2VkIDYsIDQsIDUgaW4gb25lIGdyb3VwLCBhbmQgNSwgNSwgNSBpbiB0aGUgb3RoZXIsIHdoaWNoIGdpdmVzIHVzIHRoZSBjaGVhcGVzdCBjb21iaW5hdGlvbi48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

- 내림차순으로 정렬하여 값을 세개씩 묶어 그 중 더 작은 값을 제외한 나머지를 저장한다.

코드

# https://www.acmicpc.net/problem/11508
# 접근 방법
# 내림차순으로 정렬하여 값을 세개씩 묶어 그 중 더 작은 값을 제외한 나머지를 저장한다.
n=int(input())
arr=sorted([int(input()) for _ in range(n)],reverse=True)
print(sum([arr[i] for i in range(n) if (i+1)%3>0]))