[JAVA] 백준 11062 - 카드게임

문제

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

해결 방법

• DP 알고리즘을 사용해서 풀어야 함
• 먼저 뽑는 근우를 playerA라 하고, 나중에 뽑는 명우를 playerB라고 하고
• dp[ i ][ j ] = i ~ j 번째 카드가 남았을 때 playerA의 최대값으로 가정하면 dp[ 1 ][ n ]이 정답이 됨
• 1장 남았을 때부터 n장 남았을 때까지 거꾸로 생각해보자
• dp[ i ][ j ]를 구하려면 dp[ i + 1 ][ j ]와 dp[ i ][ j - 1 ] 값을 알아야 함
• ex) 2
  4번째 카드가 남았다면 => 3
  4번째 카드가 남은 상태에서 2번째 카드를 고른 경우와 2~3번째 카드가 남은 상태에서 4번째 카드를 고른 경우
  • 위 2가지 경우를 고려
• dp 배열은 playerA의 최대값을 나타내므로, playerA 차례때는 최대, playerB 차례에는 최소가 되게끔 선택 해야함
• n이 짝수인 경우와 홀수인 경우 나눠서 생각을 해봄 (마지막에 뽑는 사람이 달라지기 때문)
• ex 1 ) n = 4 (짝수, playerB가 마지막에 뽑음) => [1, 2, 5, 2] 인 상황

• 카드가 한 장 남은 경우부터 생각을 해보자
• n이 짝수일 때, 카드가 한장 남았다면 playerB 차례
• playerB가 한 장을 가져간다면 playerA는 0점 획득

• 다음으로는 카드가 두 장 남은 상황 (playerA 차례)
• dp[1][2] = dp[1][1] + 2, dp[2][2] + 1 중 큰 값
• dp[2][3] = dp[2][2] + 5, dp[3][3] + 2 중 큰 값
• dp[3][4] = dp[3][3] + 2, dp[4][4] + 5 중 큰 값

• 다음으로는 카드가 세 장 남은 상황 (playerB 차례)
• dp[1][3] = dp[1][2], dp[2][3] 중 작은 값 + 0
• dp[2][4] = dp[2][3], dp[3][4] 중 작은 값 + 0

• 마지막으로 카드가 네 장 남은 상황 (playerA 차례)
• dy[1][4] = dy[1][3] + 2, dy[2][4] + 1 중 큰 값 => 정답

• ex 2 ) n = 5 (홀수, playerA가 마지막에 뽑음)
• [1, 4, 3, 2, 5] 인 상황
• 카드가 한 장 남았을 때는 playerA 차례

• playerA 선택 후

• playerB 선택 후

• playerA 선택 후

• playerB 선택 후

• playerA 선택 후 => 정답 : 9
• 점화식을 생각해보면
  • playerB 차례일때는 dp[ i ][ j ] = dp[ i + 1 ][ j ], dp[ i ][ j - 1] 중 작은값
  • playerA 차례일때는 dp[ i ][ j ] = dp[ i + 1 ][ j ] + arr[ i ], dp[ i ][ j - 1 ] + arr[ j ] 중 큰 값

코드

import java.util.Scanner;

public class p11062 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        for(int tt = 0 ; tt < t ; tt ++) {
            int n = sc.nextInt();
            int[][] dp = new int[n + 2][n + 1];
            int[] arr = new int[n + 1];

            for(int i = 1 ; i <= n ; i ++) {
                arr[i] = sc.nextInt();
            }

            boolean playerATurn = true;
            if(n % 2 == 0) {
                // 카드가 짝수개이면 마지막에 playerB가 뽑음
                playerATurn = false;
            }

            for(int i = 1 ; i <= n ; i ++) {
                for(int j = 1 ; j <= n - i + 1 ; j ++) {
                    // 대각선으로 내려가는 로직 => dp[j][i + j - 1]
                    int row = j;
                    int col = i + j - 1;

                    if(playerATurn) {   // playerA 차례에는 최대한 크게
                        dp[row][col] = Math.max(dp[row + 1][col] + arr[row], dp[row][col - 1] + arr[col]);
                    } else {        // playerB 차례에는 최대한 작게
                        dp[row][col] = Math.min(dp[row + 1][col], dp[row][col - 1]);
                    }
                }
                playerATurn = !playerATurn;
            }

            System.out.println(dp[1][n]);
        }
    }
}