실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 128 MB |
수진과 지훈은 동전을 가지고 재미있는 게임을 하기로 했습니다. 동전들은 각각 서로 다른 가치를 가지고 있으며, 이 동전들로 이루어진 라인을 앞에서부터 혹은 뒤에서부터 차례대로 하나씩 가져가며 게임을 합니다.
총 N (1 <= N <= 5,000) 개의 동전이 있고, 각 동전의 가치는 C_i (1 <= C_i <= 5,000)로 표시됩니다. 동전은 직선으로 놓여있습니다. 수진과 지훈은 번갈아가면서 동전을 가져갑니다. 자신의 차례가 되면, 한 번에 라인의 맨 앞이나 맨 뒤에 있는 동전 하나를 가져갈 수 있습니다. 동전이 모두 없어질 때까지 게임은 계속됩니다.
수진과 지훈는 각자 자신이 가져간 동전의 가치의 총합이 최대가 되도록 열심히 게임을 합니다. 수진이 먼저 게임을 시작합니다.
두 사람이 각자 최적의 전략으로 게임을 진행한다고 가정했을 때, 수진이 얻을 수 있는 동전 가치의 최대 총합을 얼마인지 계산해주세요.
예를 들어, 다음과 같은 값이 있는 네 개의 동전이 일렬로 놓여 있는 게임을 생각해봅시다:
30 25 10 35
이 게임의 순서는 다음과 같습니다:
수진 지훈 New Coin
Player Side CoinValue Total Total Line
수진 Right 35 35 0 30 25 10
지훈 Left 30 35 30 25 10
수진 Left 25 60 30 10
지훈 Right 10 60 40 --
이것이 수진이 할 수 있는 최선의 게임입니다.
4 30 25 10 35
60