質問する

https://www.acmicpc.net/problem/9465

マイコード(答えを参照)

"""
1. 아이디어

2. 시간복잡도
O(N-2)정도? n이 2이상일때
"""

from sys import stdin
input = stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())

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

    # n = 1 인 경우
    if n == 1:
        print(max(dp[0][n-1], dp[1][n-1]))
        continue

    # n = 2 이상인 경우
    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]))

    

に感銘を与える

nが1の場合
2つのシールが隣接しているので、2つのシールの中で高い点数を出すことができます.

nが2の場合

最後のインデックス1の観点から、赤色チェックの値または青色チェックの値のうち、より高いスコアが出力されます.

nが3より大きい場合は

である.

最後のインデックス2の観点から、2つの赤色マーカーのうちの1つに1つまたは青色マーカーのうちの1つに1つを加えた値には、高いスコアが出力されます.
このとき、インデックス1の値には、nが2の場合のプロシージャを表すステータス値が含まれます.
nが2より大きい場合、最後のインデックスnは
別のローインデックスn−1またはn−2の値のうち、大きな値が候補であることがわかる.

参考資料

https://ye333.tistory.com/entry/%EB%B0%B1%EC%A4%80python-9465%EB%B2%88-%EC%8A%A4%ED%8B%B0%EC%BB%A4