백준 9465 : 스티커 (Python)

본문링크

import sys
input=sys.stdin.readline

for _ in range(int(input())):

    N=int(input())
    L=[ [0,0] + list(map(int,input().split())) for _ in range(2)  ]
    L.insert(0 , [0]*(N+2) )
    dp=[ [0]*(N+2) for _ in range(3) ]

    for i in range(2,N+2):
        dp[1][i] = max(L[1][i] + L[2][i-1] + dp[1][i-2] , dp[1][i-1] , L[1][i] + dp[2][i-1] )
        dp[2][i] = max(L[2][i] +  L[1][i-1] + dp[2][i-2]  , dp[2][i-1] , L[2][i] + dp[1][i-1])

    print(max(dp[1][-1] , dp[2][-1]))

📌 어떻게 풀것인가?

다이나믹 프로그래밍 기법을 활용했습니다.
오랜만에 $dp$ 문제를 풀려고 하니 좀 많이 어려웠습니다.

점화식 부터 하나씩 봅시다.

• dp[1][i] = max(L[1][i] + L[2][i-1] + dp[1][i-2] , dp[1][i-1] , L[1][i] + dp[2][i-1] )

• L[1][i] + L[2][i-1] + dp[1][i-2] : 현재 위치의 스티커 선택 + 아래위치의 이전 스티커 선택 + 현재 위치의 두번째 이전의 값

  

• dp[1][i-1] : 스티커를 선택하지 않는 경우

  

• L[1][i] + dp[2][i-1] : 현재 스티커를 선택하고 아래위치의 이전값

만약 현재 점수가 100점인 위치에 왔다고 가정해봅시다.
총 2가지 선택지가 있습니다.

• 스티커를 선택하는 경우

스티커를 선택했을때 상하좌우의 스티커 값은 얻지못합니다.
따라서 현재 위치의 2번째의 최대값 + 현재 위치에 스티커의 값 + 아래 위치의 i-1 번째 스티커의 값이 점화식이 됩니다.

또는 현재 위치에 스티커의 값 + 아래쪽의 i-1 번째 의 최대값을 선택할 수 있ㅅ브니다.

• 스티커를 사용하지 않는 경우

$dp$ 테이블의 이전 값을 그대로 사용합니다.

• dp[2][i] = max(L[2][i] + L[1][i-1] + dp[2][i-2] , dp[2][i-1] , L[2][i] + dp[1][i-1])

  • L[2][i] + L[1][i-1] + dp[2][i-2] : 현재위치의 스티커와 위쪽 위치의 이전스티커 선택 + 현재 위치의 두번째 이전의 값
  • dp[2][i-1] : 스티커를 선택하지 않는 경우
  • L[2][i] + dp[1][i-1] : 현재위치의 스티커를 선택하고 위쪽 위치의 이전의 값

아래쪽인 경우도 위쪽일때와 마찬가지로 점화식을 세워주면 됩니다.