백준(BOJ) 11062 카드 게임(Python)

문제 내용.

 

DP 문제.

결국 끝까지 가서 상태를 봐야하기 때문에 그리디하게는 풀 수 없고, 백트래킹을 하자니 n이 너무 커서 DP를 생각했다.

i번째부터 j번째까지의 카드를 뽑은 상태에서 근우가 가질 수 있는 최선의 점수를 저장하는 배열을 DP로 생성하자.

DP[0][n-1]이 0부터 n-1번째까지 카드를 근우가 먼저 뽑은 경우가 되어야 하므로,

DP[0][n-2]는 0부터 n-2번째까지 카드를 명우가 먼저 뽑은 경우가 될 것이다.

그렇게 순서를 결정해나가면 처음에 카드를 뽑는 것은 n이 홀수일 때에는 근우가 먼저, 짝수일 때는 명우가 먼저인 것을 알 수 있다.

그럼 이제 DP를 채우는 점화식을 생각해보자.

DP[i][j]는 근우가 카드를 뽑을 차례인 경우와 명우가 카드를 뽑을 차례인 경우로 나눠 생각해야 한다.

근우가 카드를 뽑을 차례인 경우에는 현재 구간의 양 쪽 끝을 각각 고르는 경우를 비교해야하기 때문에 max(DP[i][j-1]+L[j],DP[i+1][j]+L[i])로 채우고, 명우가 카드를 뽑을 차례인 경우에는 근우가 뽑은 수가 더 작은 쪽으로 고르는 것이 명우에게 이득이므로 min(DP[i][j-1],DP[i+1][j])로 채우면 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
for _ in range(int(input())):
    n=int(input())
    L=list(map(int,input().split()))
    DP=[[0 for i in range(n)] for j in range(n)]
    flag=1 if n%2==0 else 0
    if not flag:
        for i in range(n):
            DP[i][i]=L[i]
    for i in range(n-1):
        for j in range(n-(i+1)):
            if flag:
                DP[j][i+j+1]=max(DP[j][i+j]+L[i+j+1],DP[j+1][i+j+1]+L[j])
            else:
                DP[j][i+j+1]=min(DP[j][i+j],DP[j+1][i+j+1])
        flag^=1
    print(DP[0][n-1])

pypy로 제출했다.