[python] 백준 10835 카드게임

https://www.acmicpc.net/problem/10835

10835번: 카드게임

 

문제 해결

• 사실 처음에 DFS를 이용해서 완전탐색을 하면 쉽게 풀 수 있겠다 싶었다.
• 하지만 DFS의 시간복잡도는 $O(2^{N})$ 이며 1≤$N$≤2,000이기 때문에 매우 복잡해질 수 있었고 시간초과로 부분점수밖에 얻지 못했다.
• 사실 숫자가 크고 완전탐색이 필요한 경우는 대부분 DP로 푸는 경우였다.
• 우선 왼쪽 카드 중 가장 큰 수가 오른쪽 카드 중 가장 큰 수보다 크면 오른쪽 카드를 다 더한 값이 정답이 된다는 것은 쉽게 알 수 있다.
• 만약 그렇지 않을 때는 완전탐색을 해서 가장 좋은 답을 찾아야한다.
• (i,j)에서 일반적으로 2가지 행동은 무조건 할 수 있다. 두 카드 모두 버리는거, 왼족 카드만 버리는 것 이 때 점수를 얻지 못하므로 dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])가 되고 dp[i+1][j] = max(dp[i+1][j], dp[i][j])가 된다.
• 하지만 왼쪽 카드(A[i])가 오른쪽 카드(B[j])보다 크다면 dp[i][j+1] = max(dp[i][j+1], dp[i][j]+B[j])가 된다.
• 따라서 dp에서 $n$행 중 가장 큰 값과 $n$ 열 중 가장 큰 값을 비교해서 가장 큰 값이 정답이 된다.

 

CODE

import sys
input = sys.stdin.readline


def DP():
    dp = [[-1 for _ in range(n+1)] for _ in range(n+1)]    
    dp[0][0] = 0
    for i in range(n):
        for j in range(n):
            if dp[i][j] > -1:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
                dp[i+1][j] = max(dp[i+1][j], dp[i][j])
                if A[i] > B[j]:
                    dp[i][j+1] = max(dp[i][j+1], dp[i][j]+B[j])
    return dp

def solution():
    if max(A) > max(B):
        print(sum(B))
        return
    dp = DP()
    answer = max(max(dp[-1]), max([_dp[-1] for _dp in dp]) )
    print(answer)
if __name__=='__main__':
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    solution()