[백준] 9465 : 스티커 (Python)

정답코드

import sys
input = sys.stdin.readline


for _ in range(int(input())):
    n = int(input())
    s = [list(map(int, input().split())) for _ in range(2)] # 스티커 점수 배열
    dp = [[e for e in x] for x in s] # 스티커 점수 배열 복사
    for y in range(n):
        for x in range(2):
            for xx in range(2):
                for yy in range(max(y-2,0),y):
                    if abs(x-xx)+abs(y-yy) > 1:
                        dp[x][y] = max(dp[x][y], dp[xx][yy]+s[x][y])
    print(max(max(dp[0]),max(dp[1])))

풀이

다음 예시를 보자.

50 10 100 20 40
30 50 70 10 60

왼쪽 위(50)부터 시작해서 50->30->10->50 이 위치대로 dp를 채워나간다.
1.dp를 위 예시 배열과 동일하게 초기화
2.자신보다 왼쪽 스티커들과의 조합 중에서 거리가 2(바로 옆이 아님) 이상인 스티커들과의 배열 중에서 최댓값(max함수를 이용하여 계속 업데이트)에 자신을 포함시킨다.