백준[10835] 카드게임 (Python3)

처음에 잘못 생각해서 그리디하게 풀다 반례를 못찾아서 고통받았다
태그 확인해보니 dp여서 많이 당황했던 문제

그리고 몰랐는데, 파이썬으로 재귀 호출 10^ 6으로 하면 바로 메모리 초과 나더라.
10^6이 생각보다 메모리 공간을 많이 먹는듯

룰을 분석하면 3가지다.
1. 왼쪽만 버린다.
2. 왼쪽, 오른쪽 둘 다 버린다. (점수 X)
3. 왼쪽 > 오른쪽인 경우 오른쪽을 버린다. (점수 O)

처음 상태부터 경우의 수를 키워나가는 것이 편하게 풀 수 있다 생각해 bottom-up 방식으로 풀었다.
재귀함수의 기저는 왼쪽 또는 오른쪽의 카드 더미가 0일 때이고,
기존에 계산된 값이 있다면 그 값을 반환한다.

이제, 왼쪽 상단과 오른쪽 상단을 비교해
오른쪽이 크다면, 오른쪽 상단을 버리고
그게 아니라면, 둘다 버리거나, 왼쪽만 버릴 때 무엇이 더 큰지를 비교해나간다.

import sys
sys.setrecursionlimit(10 ** 5)
N = int(input())
left  = list(map(int, input().split()))
right = list(map(int, input().split()))
dp = [[-1 for _ in range(N)] for _ in range(N)]

def recur(l, r):
    if l == N or r == N:
        return 0
    if dp[l][r] > -1:
        return dp[l][r]
    if left[l] > right[r]:
        dp[l][r] = max(dp[l][r], recur(l, r + 1) + right[r])
    else:
        throwBoth = recur(l + 1, r + 1)
        throwLeft = recur(l + 1, r)
        dp[l][r] = max(dp[l][r], throwBoth, throwLeft)
    return dp[l][r]


print(recur(0, 0))