[BOJ] 9465. 스티커(python)

📌문제

💪아이디어

1. 하나의 스티커를 선택하면 상하좌우에 있는 스티커는 선택할 수 없다. 그래서 현재 스티커에서 북서쪽이나 남서쪽에 있는 스티커를 고르거나 한칸 뒤쪽 북서나 남서쪽 스티커를 고를 수 있다.
   

2. 세 번째 스티커부터 두 가지 선택지가 있다.
   

3. 2번을 선택하는 경우에는 이미 1.에서 고른 스티커의 점수를 더한 값이기 때문에 해당 스티커 점수와 2번 스티커점수를 더하면 된다.
   

4. 최대 스티커 점수 고르기
   1열에 있는 스티커와 2열에 있는 스티커를 고르는 경우가 서로 다르기 때문에 1열과 2열의 마지막번째에 있는 스티커의 총합을 비교한다.
   

   🥂코드

import sys; input = sys.stdin.readline

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

    n = int(input())
    stickers = []

    for i in range(2):
        stickers.append(list(map(int,input().split())))

    stickers[0].insert(0,0)
    stickers[1].insert(0,0)

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

    print(max(stickers[0][n],stickers[1][n]))