Informatica Online Judge

  카드게임 [1379 / 0563]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 18   Total Tried : 27


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[ACM ICPC 2015]

Background

숫자(1<=x<=10000)가 적혀있는 N개(1<=N<=1000)의 카드가 일렬로 놓여있다.

더 이상 가져갈 카드가 남아 있지 않을때까지 두 사람이 번갈아가면서 가장 왼쪽 카드나 가장 오른쪽 카드를 하나씩 선택한다.

당연히 이 게임은 서로 이기기 위해서 최선을 다한다.

최종적으로, 자신이 선택한 카드의 숫자의 합이 크면 이기는 게임이다. 첫 번째 카드를 선택한 player에게 나올 수 있는 최대 숫자합을 구하시오.

예를 들어, [1, 2, 5, 2] 카드가 뒤집혀서 일렬로 놓였다면 첫번째 player의 최대 숫자합은 6이다.

p1 : 1을 가지고 간다. 남은 카드 [2 5 2]
p2 : 오른쪽의 2를 가지고 간다. 남은카드 [2 5]
p1 : 5를 가지고 간다. 남은 카드 [2]
p2 : 2를 가지고 간다.

따라서 p1이 가져간 카드는 1 + 5 = 6 이고, 이보다 더 큰 점수를 얻는 방법은 없다.

Input

첫째줄에는 일렬로 나열된 카드 개수를 입력한다.
카드에 적혀있는 숫자는 자연수로 빈 칸을 사이에 두고 입력된다.

[입력값의 정의역]
1 <= N <= 1,000
1 <= x <= 10,000

Output

첫 번째 카드를 선택한 플레이어에게 나올 수 있는 최대 합을 출력한다.

IO Example

입력1
4
4 3 1 2

출력1
6

입력2
9
1 1 1 1 2 2 2 2 2

출력2
8

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]