[BOJ]9465シール


📃 シール枚

コード#コード#

t = int(input())

for i in range(t): #전체 테스트 횟수
    col = int(input())
    graph=[]
    for j in range(2): #row은 항상 2줄
        graph.append(list(map(int, input().split())))

    graph[0][1] += graph[1][0]
    graph[1][1] += graph[0][0]

    for k in range(2, col):
        graph[0][k] += max(graph[1][k-1], graph[1][k-2])
        graph[1][k] += max(graph[0][k-1], graph[0][k-2])

    print(max(graph[0][col-1], graph[1][col-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の値のうち、大きな値が候補であることがわかる.