지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.
이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.
언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
(1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.
다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다
카드 순서
왼쪽 더미
오른쪽 더미
1
3
2
2
2
4
3
5
1
이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다.
만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다.
이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다.
만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다.
이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다.
이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다.
이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다.
두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최대값을 출력하는 프로그램을 작성하시오.
위 예에서 최종 점수의 최대값은 7이다.
입력
첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1 ≤ B ≤ 2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.
근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다.
근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오.
예를 들어 카드가 [4, 3, 1, 2]로 놓여있다고 하자. 근우는 처음에 4가 적힌 카드를 가져가고, 명우는 3이 적힌 카드를 가져간다. 그리고 근우는 2가 적힌 카드를 가져가고, 명우는 마지막으로 1이 적힌 카드를 가져간다. 이 때 근우와 명우는 최선의 전략으로 임했으며, 근우가 얻는 점수는 6이다.
입력
입력의 첫 줄에는 테스트케이스의 수 T가 주어진다.
각 테스트케이스 마다 첫 줄에는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N개의 자연수가 공백으로 구분되어 주어지는데, i번째로 주어지는 수는 왼쪽에서 i번째에 놓인 카드에 적힌 수를 의미한다. 카드에 적혀있는 수는 1이상 10,000이하다.
출력
각 테스트케이스마다 근우와 명우가 최선의 전략으로 임할 때 근우가 얻게되는 점수를 줄로 구분하여 출력한다.
예제 입력
2
4
1 2 5 2
9
1 1 1 1 2 2 2 2 2
예제 출력
6
8
1. 접근
두 명이 일련의 규칙에 따라 게임을 진행한다.
단 둘다 최선의 전략을 알고 있다 가정할 때(최선의 전략이 뭔지는 아직 모른다),
선 턴인 주인공이 최대로 얻을 수 있는 점수는 몇 점일까?
계속되는 알고리즘 게임의 일종으로, 아무리 짱구를 굴려봐도 최선의 전략이 무엇일지는 감이 안오므로,
모든 경우를 계산해보는(하지만 빠른) 다이나믹 프로그래밍으로 풀어보자.
2. 풀이
dp[turn][남은 카드들 중 왼쪽 끝][남은 카드들 중 오른쪽 끝]으로 배열을 잡아보자.
턴은 번갈아 진행되며, 남은 카드들의 양 쪽 끝은 0 ~ n-1 까지다.
다이나믹 프로그래밍으로 한 번 기록된 dp배열에 접근하면 상수시간에 리턴되므로 배열 크기에 비례한 O(2*n*n)에 풀 수 있겠다.
이제 문제를 풀어줄 함수를 정의해보자.
func(int turn, int x, int y) = 턴이 turn이고, 왼쪽 끝은 x, 오른쪽 끝은 y 일 때 내가 얻을 수 있는 최대의 점수.
우리는 이제 기저사례로 x==y인 경우를 생각해 볼 수 있다.
남은 카드가 한 장이란 말로, 내 턴이였다면 점수를 취하고, 상대 턴이라면 "그냥 그랬구나" 하고 넘어가면 된다.
이제 왼쪽을 가져가든지, 오른쪽을 가져가든지 점수가 얼마나 될지 계산해봐야 한다.
내 턴이였다면 실제로 점수 계산을 위한 코드가 있어야 할테고,
상대 턴이였다면, 상대도 최선의 전략으로 플레이하기 때문에 양 쪽 플레이 중 나의 점수를 최소로 하는 플레이를 할 것이다.
3. 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
#include<string.h>
#include<algorithm>
usingnamespacestd;
#define my 0
int dp[2][1001][1001];
int arr[1001];
int t, n, i;
int func(int turn, int x, int y) {
if (x == y) {
if (turn == my)
return arr[x];
else
return0;
}
int& ref = dp[turn][x][y];
if (ref !=-1)
return ref;
if (turn == my)
ref = max(func(turn ^ 1, x +1, y) + arr[x], func(turn ^ 1, x, y -1) + arr[y]);
else
ref = min(func(turn ^ 1, x +1, y), func(turn ^ 1, x, y -1));
