algospot :: NUMBERGAME 숫자게임

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

알고리즘 문제 해결 전략 p.342

[알고리즘 STEP. 1]

어차피 숫자를 양 끝에서만 지울 수 있으므로, 지워진 숫자들을 고려할 범위 밖으로 밀어내는 방식으로 지울 수 있다.

예를들어 처음에 5개 숫자가 들어왔다면 인덱스 0, 1, 2, 3, 4를  다 고려하다가

왼쪽에서 하나를 지웠으면 1,2,3,4만,

오른쪽에서 두개를 또 지우면 1,2 만

이렇게 남은 인덱스들만 고려하여 문제를 풀면 된다.

남은 숫자 중 왼쪽 끝 인덱스를 st, 오른쪽 끝 인덱스를 ed로 잡고 다음 함수를 작성하였다.

*int play(int st, int ed)

이미 st부터 ed까지 남은 인덱스에서 게임을 플레이했다면 캐시에서 해당 값을 가져온다.

안했으면, 플레이해서 캐시에 값을 저장하는데,

1. if(st+2 <= ed) ret = max(ret, play(st+2, ed));

만약 왼쪽에 두개  이상 남았으면 왼쪽 2개 지우고 턴 바꿔서 플레이

2. if(st <= ed-2) ret = max(ret, play(st, ed-2));

만약 오른쪽에 두개 이상 남았으면 오른쪽 2개 지우고 턴 바꿔서 플레이

3. if(st+1<=ed) ret = max(ret, play(st+1, ed)+board[st]);

만약 왼쪽에 하나 이상 남았으면 왼쪽 한개를 현재 사람이 먹고, 턴 바꿔서 플레이

이 때 리턴 값은 원래것 + 지금 먹은 숫자

4. if(st <= ed-1) ret = max(ret, play(st, ed-1)+board[ed]);

만약 왼쪽에 하나 이상 남았으면 오른쪽 한개를 현재 사람이 먹고, 턴 바꿔서 플레이

이 때 리턴 값은 원래것 + 지금 먹은 숫자

다음 플레이를 할 때는 턴이 바뀌므로 리턴값에 -를 취해준다. ret = -ret;

(이 부분은 tictactoe문제에서 다뤘었다.)

[최종코드]

#include <iostream> #include <limits> #include <string.h> #define FOR(i, ed) for(int i = 0 ; i < ed; i++) using namespace std; //input int tc, n; int board[50]; //solve int cache[50][50]; int play(int st, int ed){ if(st == ed) return -board[st]; int& ret = cache[st][ed]; if(cache[st][ed] != -1) return ret; ret = numeric_limits<int>::min(); if(st+2 <= ed) ret = max(ret, play(st+2, ed)); if(st <= ed-2) ret = max(ret, play(st, ed-2)); if(st+1<=ed) ret = max(ret, play(st+1, ed)+board[st]); if(st <= ed-1) ret = max(ret, play(st, ed-1)+board[ed]); ret = -ret; return ret; } int main(){ // freopen("input.txt", "r", stdin); cin >> tc; while(tc--){ memset(cache, -1, sizeof(cache)); cin >> n; FOR(i, n){ cin >> board[i]; } cout << -play(0, n-1) << endl; } }

지운 숫자를 다음 턴에 어떻게 넘겨줄까만 잘 떠올리면 되는 문제인 것 같다.