[백준 11062] 카드 게임 (python)

11062번: 카드 게임

 

---

 

DP를 사용하는 문제이다. 시간초과가 나서 Pypy3으로 제출하였다.

최선을 다해 게임에 임한다는 것이 이해하기 너무 힘들었다. 

dp[i][j]는 i번째 카드부터 j번째 카드로 게임을 할때 [1번째로 뽑는 사람 점수, 2번째로 뽑는 사람 점수]를 저장해준다.

 

카드게임을 할 때 왼쪽카드를 가져가거나 오른쪽 카드를 가져가는 방법이 있다.

 

1. 왼쪽 카드를 뽑을 때

처음 사람은 왼쪽 카드(1)와 나머지카드(2,5,2)에서 2번째로 뽑는 사람의 점수를 합한 것이다.

다음 사람은 나머지 카드(2,5,2)에서 1번째로 뽑는 사람의 점수이다.

 

2. 오른쪽 카드를 뽑을 때

처음 사람은 오른쪽 카드(2)와 나머지카드(1,2,5)에서 2번째로 뽑는 사람의 점수를 합한 것이다.

다음 사람은 나머지 카드(1,2,5)에서 1번째로 뽑는 사람의 점수이다.

 

1. 카드의 정보를 cards 배열에 저장한다.
2. pickCard는 cards에서 i번째부터 j번째 카드가 있을 때 카드를 선택하는 함수이다.
3. 이미 정보가 있다면 리턴해준다.
4. 카드가 한장이라면(i==j) 1번째 사람만 가져가므로 [카드 점수, 0] 를 리턴해준다.
5. 위에서 설명했듯이 score를 계산해준 후, 1번째로 뽑은 사람과 2번째로 뽑은 사람의 점수를 dp에 저장해준다.
6. 카드 0~N-1에서 1번째로 뽑는 사람의 점수 값을 출력해준다.

 

import sys
input = sys.stdin.readline
 
 
def pickCard(cards, i, j):
    if dp[i][j]:
        return dp[i][j]
 
    if i == j:
        dp[i][j] = [cards[i], 0]
        return dp[i][j]
 
    first1, second1 = pickCard(cards, i+1, j)
    score1 = second1 + cards[i]
 
    first2, second2 = pickCard(cards, i, j-1)
    score2 = second2 + cards[j]
 
    if score1 > score2:
        dp[i][j] = [score1, first1]
    else:
        dp[i][j] = [score2, first2]
 
    return dp[i][j]
 
 
T = int(input())
for _ in range(T):
    N = int(input())
    dp = [[None for _ in range(N+1)] for _ in range(N+1)]
    cards = list(map(int, input().split()))
    print(pickCard(cards, 0, N-1)[0])