무민은귀여워

[알고스팟] 숫자 게임 NUMBERGAME 본문

IT/알고리즘

[알고스팟] 숫자 게임 NUMBERGAME

moomini 2019. 11. 19. 16:47
반응형

https://algospot.com/judge/problem/read/NUMBERGAME

 

algospot.com :: NUMBERGAME

숫자 게임 문제 정보 문제 n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있습니다. 게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다. 게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지웁니다. 게임은 모든 숫자가

algospot.com

 

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int EMPTY = -987654321;
int N, board[50];
int cache[50][50];
 
int dp(int left, int right) 
{
 
    if (left > right)
    {
        return 0;
    }
 
    int& ret = cache[left][right];
 
    if (ret != EMPTY)
    {
        return ret;
    }
 
    ret = max(board[left] - dp(left + 1, right), board[right] - dp(left, right - 1));
 
    if (right - left + 1 >= 2) 
    {
        ret = max(ret, -dp(left + 2, right));
        ret = max(ret, -dp(left, right - 2));
    }
 
    return ret;
}
 
int main() 
{
    int T; 
    scanf_s("%d", &T);
 
    while (T--) 
    {
        int N; scanf_s("%d", &N);
 
        for (int i = 0; i < N; ++i)
        {
            scanf_s("%d", &board[i]);
        }
 
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                cache[i][j] = EMPTY;
            }
        }
 
        printf("%d\n", dp(0, N - 1));
    }
 
    return 0;
}
 cs

 

반응형

'IT > 알고리즘' 카테고리의 다른 글

[백준]1339 단어 수학  (0) 2021.05.17
Bubble(버블 정렬), Insertion(삽입 정렬), Quick(퀵 정렬) 소스  (0) 2019.11.27
[코딩인터뷰] 자료구조  (0) 2019.11.22
[알고스팟] 울타리 잘라내기 FENCE  (0) 2019.11.19
[알고스팟] 쿼드 트리 뒤집기 QUADTREE  (0) 2019.11.19
'IT/알고리즘' Related Articles more
Comments