백준 11062번 카드 게임(JAVA)

문제

11062번: 카드 게임

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    private static int[] cards;
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;

        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            cards = new int[N];
            map = new int[N + 1][N + 1];
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                cards[j] = Integer.parseInt(st.nextToken());
            }

            func(0, N - 1, true);

            System.out.println(map[0][N - 1]);
        }
    }

    private static int func(int left, int right, boolean turn) {
        if (left > right) { // 왼쪽 인덱스가 오른쪽 인덱스보다 커졌을 때. 즉, 더이상 남은 카드가 없으면 그냥 종료한다.
            return 0;
        }

        if (map[left][right] != 0) { // 이미 계산된 값일 때.
            return map[left][right];
        }

        if (turn) { // 근우 차례일 때, 어느 쪽 카드를 고르는 것이 최대값을 가지는지 탐색한다.
            return map[left][right] = Math.max(cards[left] + func(left + 1, right, false),
                    cards[right] + func(left, right - 1, false));
        } else { // 명우 차례일 때, 어느 쪽 카드를 골랐을 때 근우가 최소값을 가져가는지 탐색한다.
            return map[left][right] = Math.min(func(left + 1, right, true), func(left, right - 1, true));
        }
    }
}