스티커 실버1 (백준, DP)

import sys

input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    starr = []
    for _ in range(2):
        temp = list(map(int, input().split()))
        starr.append(temp)

    for i in range(1, n):
      if i == 1:
        starr[0][i] += starr[1][i-1]
        starr[1][i] += starr[0][i-1]
      else:
        starr[0][i] += max(starr[1][i-1], starr[1][i-2])
        starr[1][i] += max(starr[0][i-1], starr[0][i-2])
  
    print(max(starr[0][-1],starr[1][-1]))

처음에는 dp테이블을 입력과 똑같은 크기로 초기화하고 i 이전 값들과 모두 비교해주는 과한 계산을 했다.

 

이후 대각선의 두번째 값만 한 번 더 비교해주면 되는 것을 깨달았다.