사탕 나누기

면접 대비

시간 제한2초메모리 제한512 MB

요약

n개의 상자(n은 최대 24)를 세 그룹으로 나누어 합이 A <= D <= B가 되게 하고, B - A의 최솟값을 구한다.

난이도: 보통10점 중 7점
유형: 완전 탐색, 그리디, 정렬, 비트 연산
정답자: 아직 제출이 없습니다

문제

어린이날을 맞아 어머니가 세 형제 안톤(Anton), 드미트로(Dmytro), 보리스(Borys)에게 사탕을 잔뜩 주었다. 사탕은 $n$ 개의 상자에 담겨 있고, $i$ 번째 상자에는 $a_i$ 개의 사탕이 들어 있다. 각 상자는 통째로 한 형제에게만 배정하며, $n$ 개의 상자를 남김없이 세 형제에게 나눈다.

안톤, 드미트로, 보리스가 받게 되는 사탕의 총합을 각각 $A$ , $D$ , $B$ 라 하자. 형제들은 다음 규칙에 따라 공정하게 나누려고 한다.

형은 동생보다 사탕을 더 많이 받을 수 없다. 안톤이 드미트로보다 나이가 많고, 드미트로가 보리스보다 나이가 많으므로 $A \le D \le B$ 여야 한다.
이 조건을 지키면서 보리스와 안톤이 받은 사탕 개수의 차이 $B - A$ 를 최소로 만든다.

$B - A$ 의 최소값을 구하라.

입력

첫째 줄에 상자의 개수 $n$ 이 주어진다 ( $3 \le n \le 24$ ). 둘째 줄에 각 상자에 든 사탕의 개수를 나타내는 $n$ 개의 양의 정수 $a_i$ 가 공백으로 구분되어 주어진다 ( $1 \le a_i \le 10^9$ ).

출력

안톤과 보리스가 받은 사탕 개수의 최소 차이, 즉 $B - A$ 의 최소값을 한 줄에 정수 하나로 출력한다.

예제5

예제 1
입력
```
4
5 4 7 6
```
예상 출력
```
3
```
예제 2
입력
```
3
1 1 1
```
예상 출력
```
0
```
예제 3
입력
```
3
1 2 3
```
예상 출력
```
2
```
예제 4
입력
```
6
1 2 3 4 5 6
```
예상 출력
```
0
```
예제 5
입력
```
7
1 1 1 1 1 1 1
```
예상 출력
```
1
```