카드 게임

면접 대비

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

요약

짝수 개의 카드가 일렬로 놓여 있고 두 사람이 양 끝에서 번갈아 가져간다. 먼저 하는 사람은 자신이 가져간 정수의 합을 최대화하려 하고 상대는 그 합을 최소화하려 할 때, 먼저 하는 사람이 보장할 수 있는 최대 점수를 구한다.

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

문제

알베르토와 완데를레이가 카드 게임을 한다. 정수가 하나씩 적힌 카드가 짝수 개 있고, 이 카드는 탁자 위에 한 줄로 나란히 놓여 하나의 수열을 이룬다. 먼저 알베르토가 양쪽 끝에 있는 두 카드 중 하나를 가져간다. 이어서 완데를레이가 남은 카드의 양쪽 끝 중 하나를 가져가고, 다시 알베르토가 끝에 있는 카드 하나를 가져간다. 이렇게 번갈아 진행하다가 완데를레이가 마지막 카드를 가져가면 게임이 끝난다.

먼저 시작하는 알베르토는 자신이 가져간 카드에 적힌 수의 합, 즉 자신의 점수를 최대로 만들려고 한다. 두 번째로 두는 완데를레이는 알베르토를 방해해서 알베르토의 점수를 최소로 만들려고 한다. 두 사람 모두 각자의 목표에 맞게 최선으로 둔다.

카드의 수열이 주어졌을 때, 알베르토가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하라.

입력

입력은 여러 개의 테스트 케이스로 이루어지고, 각 테스트 케이스는 두 줄이다. 첫째 줄에는 탁자 위에 놓인 카드의 개수 $N$ 이 주어진다. 둘째 줄에는 카드에 적힌 $N$ 개의 정수가 놓인 순서대로 주어진다. 테스트 케이스는 입력의 끝까지 이어진다.

제약

$2 \le N \le 10^4$
$N$ 은 짝수다
각 카드에 적힌 정수는 32비트 부호 있는 정수로 나타낼 수 있다
테스트 케이스는 20개 이하이고, 모든 테스트 케이스의 $N$ 을 더한 값은 $2 \times 10^4$ 이하다

출력

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 그 정수는 알베르토가 얻을 수 있는 점수의 최댓값이다.

예제2

예제 1

입력

예상 출력

10
7
57

예제 2
입력
```
2
1 2
```
예상 출력
```
2
```