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

길동 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남매에게 나누어줄 선물의 합계 부피를 구하는 프로그램을 작성하시오.

선물(L) timer 1s memory 256MB

선물(L) 1s 256MB