접근

다이나믹 테이블 정의

• 입력받은 스티커의 리스트가 곧 다이나믹 테이블이 된다.
• i행 j열의 값은 n = j일 때 i행 j열의 스티커를 떼어내면서 최대로 얻을 수 있는 점수를 말한다.

설명

• 아래와 같은 스티커 배열이 있다고 하자. (안의 값은 점수이다)

1. i행 0열
   • 다른 스티커를 떼어낼 수 없으므로 자기의 점수가 곧 다이나믹 테이블의 값이 된다.
   • 별도로 건드릴 필요가 없다.
2. i행 1열

• 자신의 왼쪽(i행 0열)은 떼어낼 수 없게 되므로 대각선에 위치한 다이나믹 테이블 값에 자신의 점수를 더한 값이 최대 값이 된다.

1. i행 j열 (j ≥ 2)

• 결론부터 말하면 대각선의 위치한 j-1열, j-2열의 값 중 큰 값에 자신의 점수를 더한 값이 최대값이 된다

• 왜?

• 1행 4열을 예로 들어보면 1행 4열의 스티커를 떼어내기 위해서는 1행 3열, 1행 4열을 떼어낼 수 없다.

• 즉 두 가지 경우의 수를 제외한 나머지에서 최대값을 찾아 자신의 점수를 더하면 된다.

• 그림을 그려보면 0행 3열의 다이나믹 테이블 값은 자신과 인접한 값을 제외한 모든 값을 대표한다고 할 수 있다.
• 이때 0행 2열의 값만 고려되지 않게 되므로 이를 보충해준다.
• 결과적으로 대각선 위치의 j-1열과 j-2열을 고려하면 모든 경우의 수를 고려하는 것과 같다.

• 주어진 n열까지 다이나믹 테이블을 구한 뒤에, n열의 0행과 1행 중 큰 값이 정답이 된다.

코드

import sys
input = sys.stdin.readline

if __name__=="__main__":
    T = int(input())
    for _ in range(T):
        n = int(input())
        dy = [list(map(int,input().split())) for _ in range(2)]
        for j in range(1, n):
            if j == 1:
                dy[0][1] += dy[1][0]
                dy[1][1] += dy[0][0]
            else:
                dy[0][j] += max(dy[1][j-1], dy[1][j-2])
                dy[1][j] += max(dy[0][j-1], dy[0][j-2])
        print(max(dy[0][-1], dy[1][-1]))