크리스마스 선물 - 구름LEVEL
크리스마스 선물
Quiz Info
Quiz Info
크리스마스 선물
100points
Participant
8
Solved Rate
12.5%
0
0


구름이네 부모님은 구름이 3형제에게 크리스마스를 맞아 선물을 준비했습니다.

그런데 구름이네 부모님은 일이 바쁜 탓에 마트에서 좋아보이거나 인기가 많은 상품들을 가리지 않고 여러 개 사오셨습니다.

첫째인 구름이, 둘째 하늘이, 셋째 다임이는 여러 개의 선물들을 다음과 같이 나누기로 합니다.

 1. 선물의 부피를 기준으로 나누며 선물의 개수는 중요하지 않습니다.

 2. 3형제에게 공평하도록 선물의 부피 차이는 최소한이 되도록 합니다.

 3. 선물의 부피가 똑같이 나누어지지 못하는 경우에는 첫째 - 둘째 - 셋째 순으로 부피의 합이 크도록 배분합니다.

 4. 3형제가 가지게 될 선물의 부피 합이 결정되면 셋째 - 둘째 - 첫째 순으로 선물을 선택합니다.


선물을 나누기 위한 세부적인 조건은 다음과 같습니다.

조건 1. d = (구름이 선물의 부피 합) - (다임이 선물의 부피 합) 라고 할 때 d의 값이 최소가 되어야 합니다.

조건 2. d의 값은 같지만 분배 방법이 다른 경우에는 구름이 선물의 부피 합이 적은 방법을 선택해야 합니다.


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

1, 1, 1, 4, 6, 1, 1, 1, 1

선물의 부피 합이 구름이는 6, 하늘이는 6, 다임이는 5를 가지도록 배분 했을 때 조건 1에 따라 6 - 5 = 1 로 최소가 됩니다.

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


입력

첫 줄에 선물의 개수( 3 이상 15 이하 )

다음 줄에 선물의 부피를 나타내는 n개의 정수( 공백으로 구분 )

출력

3형제 별 선물 부피의 합



Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
9
111461111
Output
665
Example 2
Input
3
2101
Output
1021
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)