[백준] 9465번 스티커 (파이썬)

난이도 : SILVER I

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

문제해결 아이디어

• 다이나이믹 프로그래밍 기법을 통하여 해결했다.
• 길이가 3이상인 숫자 배열부터는 n-1번째 (대각선), n-2번째 (나이트 이동 위치) 중 최댓값을 고르면된다. (나이트 이동위치 반대점은 n-1(대각선)에 포함되기 때문)

소스코드

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

t = int(input())

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

    if n == 1:
        print(max(dp[0][0], dp[1][0]))
        continue
    
    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][n-1], dp[1][n-1]))