건초 더미 나누기

면접 대비

시간 제한1초메모리 제한128 MB

요약

N개의 건초 더미(N은 최대 20)를 세 헛간에 나눠 담아 가장 큰 헛간 합을 최소로 만들고, 그 최솟값을 출력한다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 재귀, 백트래킹, 수학
정답자: 아직 제출이 없습니다

문제

농부 John이 건초 더미 $N$ 개( $1 \le N \le 20$ )를 새로 받았다. $i$ 번째 더미의 크기는 $S_i$ ( $1 \le S_i \le 100$ )이다. John은 이 건초 더미들을 세 개의 헛간에 최대한 공정하게 나누어 넣으려고 한다.

John은 '공정한' 분배란 가장 큰 몫을 가능한 한 작게 만드는 것이라고 정의했다. 즉, 헛간 1, 2, 3에 들어간 건초의 총 크기를 각각 $B_1, B_2, B_3$ 이라 하고 $B_1 \ge B_2 \ge B_3$ 이 되도록 정렬했을 때, John은 $B_1$ 을 최대한 작게 만들고 싶다.

각 더미는 쪼갤 수 없으며 정확히 한 헛간에만 넣어야 한다. 어떤 헛간은 비어 있어도(총 크기 0) 된다.

공정한 분배에서의 $B_1$ 값을 구하여라.

입력

첫째 줄에 건초 더미의 개수 $N$ 이 주어진다.

이어지는 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 더미의 크기 $S_i$ 가 주어진다.

출력

공정한 분배에서의 $B_1$ 값을 한 줄에 출력한다.

예제2

예제 1
입력
```
8
14
2
5
15
8
9
20
4
```
예상 출력
```
26
```
예제 2
입력
```
3
5
5
5
```
예상 출력
```
5
```