[BOJ] Q11062 카드 게임

[BOJ] Q11062 카드 게임

Question

Language: Python

Difficulty: Gold 3

해당 문제는 순서를 돌아가면서 카드를 뽑았을 때 각자 최선의 점수가 나올 수 있도록 선택하여, 첫번째 플레이어(근우)가 가장 높은 점수를 얻도록 해야하는 것이 핵심 관건이다.

단순 dfs을 통해, 각자 플레이어가 카드를 선택하는 경우를 모두 고려하게 되면 시간 내에 풀이하는 것이 불가능하다. 따라서, 해당 부분에 dp를 적용하여, 반복되는 구간에 대한 탐색을 생략할 수 있다.

아래와 같이 시작~끝에 구간에 대한 근우의 최선의 점수를 보관하고 있는 상태로 dfs을 수행하면서, start~end 구간을 처리하게 될때, 중간에 저장되어 있는 값을 활용한다.

dp[start][end]

Solution

import sys
def solution(turn,left,right):
    if left > right:
        return 0
    if dp[left][right] != 0:
        return dp[left][right]
    
    #근우 차례인 경우
    if turn == 0:
        max_score=max(solution(1-turn,left+1,right)+cards[left],solution(1-turn,left,right-1)+cards[right])
        dp[left][right]=max_score
    #명우 차례인 경우 --> 근우의 점수만을 저장하기 때문에, 명우의 점수를 더할 필요가 없다.
    else:
        min_score=min(solution(1-turn,left+1,right),solution(1-turn,left,right-1))
        dp[left][right]=min_score
    
    return dp[left][right]

if __name__ == '__main__':
    n_testcases=int(input())
    for i in range(n_testcases):
        n=int(input())
        cards=list(map(int,input().split()))
        dp=[[0] * n for _ in range(n)]
        print(solution(0,0,n-1))