[백준 11062/Python] 카드 게임

1. 문제 / 난이도 : Gold Ⅲ

www.acmicpc.net/problem/11062

11062번: 카드 게임

---

2. 풀이 및 코드 설명

전형적인 DP문제. 처음에는 근우의 입장에서만 생각하고 코드를 짠 후 당당하게 제출했는데 역시 당당하게 틀렸다. 해당 문제는 다음과 같이 근우의 차례일 때와 명우의 순서일 때를 나누어서 생각해야 한다.

 

(1) 근우의 순서일 때

    - 왼쪽 카드를 선택하고 나머지 카드들에서 얻는 점수, 오른쪽 카드를 선택하고 나머지 카드들에서 얻는 점수 중 최댓값

(2) 명우의 순서일 때

    - 왼쪽 카드 제외한 나머지 카드들에서 얻는 점수, 오른쪽 카드 제외한 나머지 카드들에서 얻는 점수 중 최솟값

    - 근우가 점수를 작게 가져가게끔 만들어야하도록 최솟값일 때의 경우를 선택

 

간단한 코드이므로 코드 블락 단위의 설명은 주석으로 대체하겠음.

---

3. 전체 코드

def pickCard(turn, i, j):
    if i > j: return 0
    if dp[i][j]: return dp[i][j] #이미 계산된 적이 있으면 해당 값 리턴
    
    #근우 차례
    if turn:
        # i카드 + (i+1~j)범위 카드의 명우 순서 or j카드 + (i~j-1)범위 카드의 명우 순서 중 최대 스코어
        score = max(pickCard(False, i+1, j) + cards[i], pickCard(False, i, j-1) + cards[j]) 
        dp[i][j] = score
        return score
        
    #명우 차례
    elif not turn:
        # (i+1~j)범위 카드의 근우 순서 or (i~j-1)범위 카드의 근우 순서 중 최소 스코어
        # 각각 명우가 i, j 카드를 가져갔다고 가정하지만, 근우 입장의 점수를 계산하는 거기 때문에 카드 점수를 더해주지 않음
        score = min(pickCard(True, i+1, j), pickCard(True, i, j-1))
        dp[i][j] = score
        return score

import sys
T = int(input()) #테스트케이스

for _ in range(T):
    N = int(input()) #카드 개수
    cards = list(map(int, sys.stdin.readline().split()))
    dp = [[0 for _ in range(N)] for _ in range(N)] #DP 배열 초기화
    pickCard(True, 0, N-1) #카드가 (0~N-1)범위만큼 있고,  근우 순서일 때 얻는 점수 계산
    print(dp[0][N-1])