난이도 : 골드 3
유형 : DP 심화
https://www.acmicpc.net/problem/11062

---

문제 접근

카드 숫자 배열이 주어졌을 때, 두명의 플레이어가 가장 왼쪽 혹은 가장 오른쪽카드를 번걸아가면서 가져갈 수 있을때, 두 명의 플레이어 모두 가장 최선의 선택을 할때, 선턴 플레이어가 가져가는 카드의 합을 출력하는 문제이다.

핵심 아이디어

처음 이 문제를 접했을 때, 그냥 선 턴 플레이어가 매 차례 양끝에서 가장 큰 값 고르면 되는 거 아니야? 했는데 아니었다.

왜냐하면 [2,100,1000,50] 이 있다치면 만약 매순간 최선을 다하는 그리디로 푼다면 50을 먼저 선턴 플레이어가 고르고 그 다음 플레이어가 1000을 고르게 되어서 선턴 플레이어는 지게된다.

그러니 선턴플레이어의 최선의 수는 50이 아닌 2를 골라서 다음 상대가 어떤 수를 고르든 1000을 골라 이기는 수이다.

그러니 매 순간 가장 큰 수를 고르는 방법은 잘못되었다.

그래서 이 문제는 단순한 그리디 방식으로 풀 수 없고,
DP (다이나믹 프로그래밍) 을 활용해서 "모든 경우의 수를 계산하면서 최적의 선택" 을 해야 한다.

DP 설계

dp[i][j]: 카드 구간 [i, j]에서 근우가 얻을 수 있는 최대 점수

size는 카드 구간의 크기

차례(turn) 는 N - size가 홀수면 근우 차례, 짝수면 명우 차례

명우도 자신의 점수를 최대화하려고 행동함 ✔️
하지만 우리는 근우가 얻을 수 있는 최대 점수만을 추적하고 있음
그래서 명우는 근우 점수를 최소화하는 방식으로 행동한다고 가정하는 것임

결국

근우 차례면 → 최댓값을 선택 (점수 더함)
명우 차례면 → 최소값을 선택 (근우 점수 줄임)

해답 및 풀이

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    arr = list(map(int, input().split()))
    dp = [[0] * N for _ in range(N)]

    turn = True if N % 2 == 1 else False  # 첫 턴이 근우 차례인지

    for size in range(N):  # 구간 크기
        for i in range(N - size):
            j = i + size
            if size == 0:
                dp[i][j] = arr[i] if turn else 0
            elif turn:  # 근우 차례
                dp[i][j] = max(dp[i + 1][j] + arr[i], dp[i][j - 1] + arr[j])
            else:       # 명우 차례
                dp[i][j] = min(dp[i + 1][j], dp[i][j - 1])
        turn = not turn  # 차례 교대

    print(dp[0][N - 1])

1. 근우 차례 (본인이 직접 선택하는 턴)
   카드 범위가 [i, j]일 때

둘 중 하나를 골라서 자기 점수에 추가하고

그 이후 명우가 남은 카드에서 최선을 다해 방해한다고 가정

dp[i][j] = max(
    arr[i] + dp[i+1][j],   # 왼쪽을 고르면 나 + 남은 구간에서 명우 차례
    arr[j] + dp[i][j-1]    # 오른쪽을 고르면 나 + 남은 구간에서 명우 차례
)

2. 명우 차례 (상대가 선택하는 턴)
   카드 범위가 [i, j]일 때

근우의 점수를 최소화하려고 한다

즉, 두 가지 경우 중 근우 점수가 더 작아지도록 선택

dp[i][j] = min(
    dp[i+1][j],   # 명우가 왼쪽을 고르면, 남은 건 [i+1, j] → 근우가 거기서 최대 점수를 가짐
    dp[i][j-1]    # 명우가 오른쪽을 고르면, 남은 건 [i, j-1]
)
```