[백준-파이썬] 9465: 스티커

문제 보러 가기!

문제

2행 n열에 한 칸마다 스티커가 있다. 각각에는 점수가 있다. 한 스티커를 쓰면, 그것과 변을 공유하는(상하좌우) 스티커를 못 쓴다. 쓸 수 있는 스터커 점수의 최댓값을 구하는 문제였다.

풀이

DP로 풀었다.

dp 테이블을 2Xn 리스트로 만들었다. 그 위치의 스티커를 뗐을 때, 그때까지의 최대 점수를 저장한다.
1행 n열의 스티커 뗐을 때의 최대 점수 = (2행 n-1열 스티커 뗐을 때의 최대 점수 or 2행 n-2열 스티커 뗐을 때의 최대 점수) + 1행 n열 스티커 점수이다.
2행 n열의 스티커 뗐을 때의 최대 점수는 위의 식에서 2행을 1행으로, 1행을 2행으로만 바꾸면 된다!

n이 1일 때, 2일 때는 따로 수작업으로 처리했다.

하늘색 숫자는 그 자리의 스티커 떼면 얻는 점수이다.
처음에 dp 1열은 무조건 arr의 숫자이다.
dp 2열은 n-2열이 아직 없으니까, n-1열만 봐준다. (연두색 화살표 참고)
dp 3열부터는 자기와 다른 행, n-1열과 n-2열 둘 중에 큰 걸 사용한다. (다른 색깔 화살표들 두 개씩 있는 것 참고)

왜 다른 행의 n-1, n-2열만 봐주고 n-3열부터는 봐줄 필요가 없을까?
만약에 dp 1행 4열을 구한다고 하면, dp 2행 3열과 dp 2행 2열 중에 큰 것에다가 arr 1행 4열의 점수를 더하면 된다.
dp 2행 1열의 경우에는, dp 2행 1열-> dp 1행 2열 -> dp 2행 3열 해서... dp 2행 3열에 그 경우가 포함되기 때문이다.

import sys

input = sys.stdin.readline  
MIIS = lambda: map(int, input().strip().split())

T = int(input())  
for _ in range(T):  
n = int(input())  
arr = list(list(MIIS()) for _ in range(2))
if n == 1:
    print(max(arr[0][0], arr[1][0]))
elif n == 2:
    print(max(arr[0][0]+arr[1][1], arr[1][0]+arr[0][1]))

else:
    dp = list([0]*n for _ in range(2))

    dp[0][0], dp[1][0] = arr[0][0], arr[1][0]
    dp[0][1], dp[1][1] = arr[0][1] + dp[1][0], arr[1][1]+dp[0][0]

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

    print(max(dp[0][n-1], dp[1][n-1]))