Informatica Online Judge

  선물 [0247 / 00F7]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 68   Total Tried : 124


The Champion of this Problem (C++) : gs16068 - ms / 754byte
My Best Submission (C++) : N/A

[]

Background

길동이는 세쌍둥이의 첫째이다. 길순이가 둘째이고, 길삼이가 막내이다.

길동 3남매의 생일을 맞이하여 전국 각지에서 친지들이 보내온 수많은 선물이 도착하였다.

길동이 부모는 이 선물들을 길동이 3남매에게 어떻게 나누어 줄 것인가로 고민하고 있다.

선물의 크고 작음 때문에 발생될 수도 있는 남매간의 다툼을 미연에 방지하고자 길동이 가족은 다음과 같이 나누기로 결정하였다.

---------------------------------------------------------------------------------------------
(1) 선물의 내용을 미리 보지 않고 부피만을 기준으로 배분한다.
(2) 한 사람이 가지는 선물의 개수는 배분의 기준이 아니다.
(3) 선물이 공평하게 나누어 질 수 있도록 3남매가 가지는 선물들의 부피의 합계에 차이가 최소가 되도록 한다.
(4) 선물의 부피가 똑같이 나누어지지 못하는 경우에는 길동-길순-길삼의 순으로 합계 부피가 많도록 배분한다.
(5) 3남매가 가지게 되는 부피가 결정되면, 길삼-길순-길동의 순으로 선물을 선택한다.
---------------------------------------------------------------------------------------------

우리가 길동 부모의 수고를 덜어주고자 길동이 3남매가 가지게 될 선물의 부피를 계산하고자 한다. 선물 부피에 따른 선물 배분의 세부적인 조건은 다음과 같다.

$조건 1$ : 아래의 $d$가 최소가 되도록 한다.

$d = (길동 선물의 부피 합) - (길삼 선물의 부피 합)$

$조건 2$: 같은 $d$가 되는 배분 방법이 여럿 존재하는 경우에는 길동의 선물의 부피 합이 적은 방법을 선택한다.

예를 들어, 선물이 $6$개이고 그 부피가 다음과 같다면,

6, 4, 4, 4, 6, 9

길동은 부피의 합계가 12, 길순은 12, 길삼은 9를 가지도록 배분하면 조건 1에 따라
$12-9=3$로 최소가 된다.

(길동 13, 길순 10, 길삼 10으로 배분하는 방법도 13-10=3으로 차이가 3이 되지만, 조건 2에 따라 답이 되지 못한다.)

선물의 부피가 입력되었을 때 3남매에게 나누어줄 선물의 합계 부피를 구하는 프로그램을 작성하시오.

Input

첫 줄에 선물의 개수를 나타내는 정수 $k$가 입력된다. ($3≤k≤20$)

다음 줄에 선물의 부피를 나타내는 $k$개의 정수가 공백으로 분리되어 입력된다.

선물의 부피는 $0$보다 크고 $100$보다 작다.

Output

길동, 길순, 길삼의 순으로 3개의 정수를 하나의 공백으로 분리하여 출력한다.

IO Example

입출력예시1>
입력
6
6 4 4 4 6 9

출력
12 12 9


입출력예시2>
입력
9
1 1 1 4 6 1 1 1 1

출력
6 6 5


입출력예시3>
입력
3
2 10 1

출력
10 2 1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]