(Python) BOJ / No. 9465 / 스티커

문제

상근의 여동생 상냥이는 문구점에서 스티커 2n개를 샀다.
스티커는 그림 (a)와 같이 2행 n열로 배열되어 있습니다.
상냥이는 스티커로 책상을 꾸며보려 합니다.

Sweetie가 산 스티커의 품질이 매우 좋지 않습니다.
스티커 하나를 떼면 옆면을 공유하는 모든 스티커가 찢어져 사용할 수 없게 됩니다.
즉, 제거된 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 됩니다.

스티커를 다 붙일 수 없는 연인은 각 스티커에 점수를 매기고 점수의 합이 최대가 되도록 스티커를 떼려고 합니다.
먼저 그림 (b)와 같이 각 스티커에 점수를 매겼습니다.
연인이 지울 수 있는 스티커의 최대 점수를 계산하는 프로그램을 작성하세요. 즉, 2n개의 스티커 중에서 면을 공유하지 않는 스티커 세트를 점수의 합이 최대가 되도록 획득해야 한다.

위 그림의 경우 점수가 50, 50, 100, 60인 스티커를 선택하면 점수가 최대 점수인 260이 됩니다.
가장 높은 점수(100점과 70점)를 가진 두 개의 스티커는 한 면을 공유하므로 동시에 제거할 수 없습니다.

해결

• dp(i)(j)는 위치 (i, j)의 스티커를 떼어냈을 때 얻을 수 있는 최고 점수라고 가정한다.
  
• 왼쪽부터 스티커를 제거했다고 가정하면 조건에 따라 재귀식은 다음과 같다.
  
  • 현재 위치에서 스티커를 제거하기 전에 얻을 수 있는 최고 점수, 즉 현재 위치의 왼쪽 대각선 아래(또는 위)에 있는 스티커를 떼어냈을 때 얻을 수 있는 최고 점수입니다.
    그리고 왼쪽에 있는 스티커를 떼면 얻을 수 있는 최고 점수.더 큰 값을 비교하고 추가합니다.
    
• 이를 재귀식으로 표현하면 다음과 같다.
  
  • dp(0)(i) = s(0)(i) + 최대(dp(1)(i – 1), dp(1)(i – 2))
  • dp(1)(i) = s(1)(i) + 최대(dp(0)(i – 1), dp(0)(i – 2))

소스 코드

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    dp = (list(map(int, input().split())) for _ in range(2))

    if n > 1:
        dp(0)(1) += dp(1)(0)
        dp(1)(1) += dp(0)(0)

        for i in range(2, n):
            dp(0)(i) += max(dp(1)(i - 1), dp(1)(i - 2))
            dp(1)(i) += max(dp(0)(i - 1), dp(0)(i - 2))

    print(max(dp(0)(-1), dp(1)(-1)))