팀 디저트

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

요약

디저트가 일렬로 놓여 있고 두 팀이 양 끝에서 번갈아 가져갈 때, 먼저 고르는 팀이 상대의 최선 대응을 가정하고 보장할 수 있는 최소 총무게를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 게임 이론, 배열, 구간
정답자: 아직 제출이 없습니다

문제

다이어트는 외롭고 지루할 수 있습니다. 그래서 Olympic Slimmers Inc.(OSI)라는 회사는 다이어트를 팀 스포츠로 만들었습니다. 이 회사의 첫 번째 게임이 바로 팀 디저트(Team Dessert) 챌린지입니다.

긴 탁자 위에 디저트 접시들이 한 줄로 놓여 있고, 각 접시에는 무게가 적혀 있습니다. 참가자들은 두 팀으로 나뉘며, 두 팀이 번갈아 가며 디저트를 하나씩 가져갑니다. 예를 들어 Red 팀과 Blue 팀이 있고 Blue 팀이 먼저 시작한다면, 가져가는 순서는 Blue, Red, Blue, Red, ... 가 됩니다.

디저트를 고르는 데에는 한 가지 규칙이 있습니다. 자신의 차례에는 줄의 양쪽 끝 중 하나에 있는 디저트만 가져갈 수 있습니다. 따라서 매 선택은 두 접시 중 하나를 고르는 것입니다(마지막 차례에는 접시가 하나만 남아 선택의 여지가 없습니다).

두 팀의 인원수는 최대한 같게 맞춥니다. 인원수를 똑같이 나눌 수 없으면 인원이 더 많은 팀이 먼저 시작합니다.
모든 참가자는 정확히 하나의 디저트를 가져갑니다.
디저트의 개수는 참가자 수와 같습니다.

디저트 무게의 합이 더 작은 팀이 승리합니다.

디저트가 놓인 순서대로 무게가 주어질 때, 먼저 시작하는 팀의 최선의 전략을 구하세요. 상대 팀도 최선으로 플레이한다고 가정할 때, 먼저 시작하는 팀이 확실하게 보장할 수 있는 최소 무게 합을 계산하면 됩니다. (이 값을 보장한다고 해서 반드시 승리하는 것은 아닙니다.)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있습니다.

각 테스트 케이스의 첫 줄에는 참가자 수를 나타내는 정수 $N$ 이 주어집니다( $1 \le N \le 1000$ ). $N = 0$ 이면 입력의 끝을 의미하며, 이는 테스트 케이스가 아닙니다.

그 다음 줄들에는 디저트가 탁자에 놓인 순서대로 $N$ 개의 무게가 주어집니다. 각 무게 $W$ 는 $1 \le W \le 100$ 을 만족합니다. 한 줄에는 무게가 적어도 하나 이상 있으며, 어떤 줄도 80자를 넘지 않습니다. 무게들은 하나 이상의 공백으로 구분되고, 줄의 앞뒤에 공백이 있을 수 있습니다.

출력

각 테스트 케이스마다, 먼저 시작하는 팀이 (상대 팀이 최선으로 플레이한다고 가정할 때) 확실하게 보장할 수 있는 최소 디저트 무게 합을 한 줄에 하나의 정수로 출력하세요.

예제5

예제 1

입력

예상 출력

19
30
11

예제 2
입력
```
1
50
0
```
예상 출력
```
50
```
예제 3
입력
```
2
1 100
0
```
예상 출력
```
1
```
예제 4
입력
```
3
1 2 3
0
```
예상 출력
```
4
```
예제 5
입력
```
2
100 1
3
3 1 2
1
42
0
```
예상 출력
```
1
5
42
```