길동이는 세쌍둥이의 첫째이다. 길순이가 둘째이고, 길삼이가 막내이다.
길동 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남매에게 나누어줄 선물의 합계 부피를 구하는 프로그램을 작성하시오.