[BaekJoon] 11062 카드 게임(Java)

1.  문제 링크

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

2.  문제

요약

• 근우와 명우는 카드 게임을 하고 있는데 N개의 카드가 일렬로 놓여 있고, 각 카드에는 점수가 적혀 있습니다.
• 근우부터 시작하여 번갈아가며 턴이 진행되는데, 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있습니다.
• 카드가 더 이상 남아있지 않을 때까지 턴은 반복됩니다.
• 게임의 점수는 자신이 가져간 카드에 적힌 수의 합입니다.
• 근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임합니다.
• 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 수 T가 주어집니다. 각 테스트 케이스마다 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 카드의 개수 N이 입력되고 두 번째 줄에 N개의 자연수가 주어집니다. i번째로 주어지는 수는 왼쪽에서 i번째에 놓인 카드에 적힌 수를 의미하고, 카드에 적혀있는 수는 1 이상 10,000 이하입니다.
• 출력: 각 테스트 케이스마다 근우와 명우가 최선의 전략으로 임할 때, 근우가 얻게 되는 점수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();

    static int N;
    static int[] cards;
    static int[][][] dp;

    static void input() {
        N = scanner.nextInt();
        cards = new int[N];
        dp = new int[2][N][N];

        for(int idx = 0; idx < N; idx++)
            cards[idx] = scanner.nextInt();
    }

    static void solution() {
        sb.append(rec_func(0, N - 1, 0)).append('\n');
    }
    
    static int rec_func(int leftIdx, int rightIdx, int turn) {
        if(leftIdx > rightIdx) return 0;

        if(dp[turn][leftIdx][rightIdx] != 0) return dp[turn][leftIdx][rightIdx];

        if(turn % 2 == 0)
            dp[turn][leftIdx][rightIdx] = Math.max(
                    rec_func(leftIdx + 1, rightIdx, 1) + cards[leftIdx],
                    rec_func(leftIdx, rightIdx - 1, 1) + cards[rightIdx]
            );
        else
            dp[turn][leftIdx][rightIdx] = Math.min(
                    rec_func(leftIdx + 1, rightIdx, 0),
                    rec_func(leftIdx, rightIdx - 1, 0)
            );

        return dp[turn][leftIdx][rightIdx];
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        while(T-- > 0) {
            input();
            solution();
        }
        System.out.print(sb.toString());
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 근우와 명우는 항상 최선의 전략으로 카드를 뽑습니다.
  • 즉, 근우는 왼쪽 카드와 오른쪽 카드 중 더 점수가 높은 카드를 뽑아야 하고, 명우는 근우가 더 낮은 점수를 갖도록 만드는 카드를 뽑아야 합니다.
• 메모이제이션을 통해 특정 카드를 뽑았을 때 점수가 몇 점인지 알 수 있는 경우를 저장해둡니다.
  • dp[turn][leftIdx][rightIdx] = turn(1일 때는 근우 차례, 1일 때는 명우 차례)에서 왼쪽에서 leftIdx 떨어진 카드까지, 오른쪽에서 rightIdx 떨어진 카드까지 선택했을 때의 점수

• 주어진 카드의 정보들을 cards라는 배열에 담고 카드 개수를 N이라고 한다면 dp 배열을 dp[2][N][N] 크기로 생성합니다.
• 재귀를 이용하여 근우가 얻게 되는 점수를 구합니다.
  • 해당 재귀 함수는 남은 카드 중 가장 왼쪽 카드의 인덱스(leftIdx), 남은 카드 중 가장 오른쪽 카드의 인덱스(rightIdx), 차례를 나타내는 수를 인자로 갖습니다(turn).
  • leftIdx가 rightIdx보다 커지는 순간은 모든 카드를 고른 경우이므로 이 때는 0을 반환합니다.
  • 만약 dp[turn][leftIdx][rightIdx]가 0이 아닌 경우는 이미 전에 해당 경우에 얻을 수 있는 점수를 구해놓은 상황이기 때문에 해당 점수를 그대로 반환합니다.
  • turn이 0이라면, 근우의 차례이므로 다음 수들 중 더 높은 수를 선택하여 해당 값을 dp[turn][leftIdx][rightIdx] 값에 할당합니다.
    • 왼쪽 카드를 선택한 경우
    • 오른쪽 카드를 선택한 경우
    • 이 때, 각 경우는 재귀를 통하여 그 이후의 선택에 대한 값을 받고 현재 선택한 카드의 점수를 더해줍니다.
  • turn이 1이라면, 명우의 차례이므로 다음 수들 중 더 낮은 수를 선택하여 해당 값을 dp[turn][leftIdx][rightIdx] 값에 할당합니다
    • 왼쪽 카드를 선택한 경우
    • 오른쪽 카드를 선택한 경우
    • 이 때, 재귀를 통하여 그 이후 선택에 대한 값을 받고 현재 선택한 카드의 점수는 더해주지 않습니다.