[c++]백준 11062 - 카드 게임(dp, 메모이제이션)

0. [c++] 백준  -

https://www.acmicpc.net/problem/11062

1. 풀이

내 턴에는 최대의 return을 찾고, 상대방의 turn에는 최소를 리턴하여 각각 최선의 플레이를 하도록 설계하고, 실제로 한장씩 카드를 선택하는 모든 경우를 탐색하도록 하자.

이미 탐색이 완료된 구간은 메모이제이션을 활용하자.

2. 소스코드

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

#include<iostream> #include<algorithm>   using namespace std;   int N; int arr[1001]; int cache[1001][1001];   int playGame(const int& front, const int& end) {     int turn = (N - (front - end)) % 2;         int& ret = cache[front][end];     if (ret != -1)         return ret;       ret = 0;     if (front == end)          if (turn)             return ret = arr[front];         return ret;       if (turn)          ret = max(playGame(front + 1, end)+arr[front], playGame(front, end - 1) + arr[end]);     else          ret = min(playGame(front + 1, end), playGame(front, end - 1));                 return ret; }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     int T;     cin >> T;     while (T--) {         cin >> N;         for (int i = 0; i < N; i++) {             cin >> arr[i];         }           for (int i = 0; i < N; i++) {             for (int j = 0; j < N; j++) {                 cache[i][j] = -1;             }         }           cout << playGame(0, N-1) << endl;     }       return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!