문제 링크: https://www.acmicpc.net/problem/10835

Thumbnail: Photo by piotr sawejko (Unsplash)

항상 느끼는 거지만 DP는 너무 어렵습니다... 좀 더 풀다보면 직관이 생기지 않을까요?

풀이

bottom-up 접근으로 풀었습니다.

DP 배열의 구성

DP[왼쪽 카드 더미의 남은 장 수][오른쪽 카드 더미의 남은 장 수] 꼴로 구성하고, DP 배열의 모든 원소를 0으로 초기화했습니다.

DP 배열 채우기

왼쪽과 오른쪽 카드 더미의 장 수는 모두 \(N\)장으로 동일합니다. DP 배열의 각 인덱스는 카드 더미의 남은 카드 수와 같으므로, \(N-1\) 부터 0까지 반복하면서 카드를 비워간다고 생각하면 이해하기 쉽습니다. 이제 DP배열을 채워봅시다.

for l in range(N-1, -1, -1):    # 왼쪽 카드 더미를 N-1장부터 0장까지 비워나간다.
  for r in range(N-1, -1, -1):  # 오른쪽 카드 더미도 마찬가지.
    if A[l] > B[r]:             # 왼쪽 카드가 오른쪽 카드보다 클 때
      # 오른쪽 카드를 한장 비우기 전의 점수 + 오른쪽 카드의 점수
      DP[l][r] = DP[l][r+1] + B[r]  # 오른쪽 카드를 버리는 경우가 항상 최댓값이다.
    else:
      DP[l][r] = max(DP[l+1][r], DP[l+1][r+1]) # 왼쪽 카드만 버리는 경우와, 둘 다 버리는 경우 중 최댓값을 이번 점수로 정한다.

print(DP[0][0]) # 반복문이 끝난 뒤, 가능한 최대 점수는 DP[0][0]에 저장된다.

전체 코드

input = open(0).readline
N = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))

DP = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

for l in range(N - 1, -1, -1):
  for r in range(N - 1, -1, -1):
    if A[l] > B[r]:
      DP[l][r] = DP[l][r+1] + B[r]
    else:
      DP[l][r] = max(DP[l+1][r+1], DP[l+1][r])

print(DP[0][0])