백준[ 9465 | Python ] 스티커

문제

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

import sys
input = sys.stdin.readline
for _ in range(int(input().rstrip())):
    n = int(input().rstrip())
    sticker = [[0]*n for _ in range(2)]
    for i in range(2):
        sticker[i] = list(map(int,(input().split())))
    for j in range(1,n):
        if j==1:
            sticker[0][j] += sticker[1][j-1]
            sticker[1][j] += sticker[0][j-1]
        else:
            sticker[0][j] += max(sticker[1][j-1],sticker[1][j-2])
            sticker[1][j] += max(sticker[0][j-1],sticker[0][j-2])
    print(max(sticker[0][-1], sticker[1][-1]))
    

생각 & 정리

기본적인 DP문제이나 2차원 배열을 사용한다는 점이 달랐다. 2차원 배열이기 때문에 가장 먼저 가장 먼저 입력되어있는 스티커의 점수를 이용하기 위해 j를 1부터 시작하고, 선택한 스티커의 변을 공유(대체로 아래, 왼쪽)하는 스티커는 사용할 수 없기 때문에, j가 1인 경우를 제외하고 max를 통해 최대 점수값을 결과로 낼 수 있도록 한다.