https://www.acmicpc.net/problem/9465
시간 1초, 메모리 256MB
input :

• 테스트 케이스의 수 T
• n (1 <= n <= 100,000)
• n개의 정수(0 <= 스티커 점수. <= 100)

output :

• 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력.

조건 :

• 스티커 한 장을 떼면, 그 스티커의 상하좌우에 있는 스티커는 모두 찢어져서 사용할 수 없게 된다

---

할 수 있는 행동 2가지 ( 윗 행일 때)
1. ➡, ⬇ / 대각선 아래로 이동.
2. ➡, ➡, ⬇ / 옆으로 2칸 이동 후 아래로 이동.

아래 행일 때.
1. ➡, ⬆ / 대각선 위로 이동.
2. ➡, ➡, ⬆ / 옆으로 2칸 이동 후 위로 이동.
옆으로 이동하는 것이 왼쪽일 수도 있다.

---

2022.01.08

다음 풀이

1. 뜯은 스티커와 변을 공유하는 스티커는 사용할 수 없다.
2. 모든 경우를?

특정 지점에서 모든 경우를 체크하는 것이 가능할까? 너무 많다. => DP를 사용
반대로 생각 특정 지점에 도착할 방법.

data[0][1]에서 data[0][3]으로 이동을 하는 경우. data[0][1] => data[0][3]으로 이동하는 것보다 아래를 거쳐서 이동하는 것이 값을 더 크게 가진다.
그렇기 때문에 위의 칼럼은 아래로, 아래에선 위로 이동을 하자

1칸 또는 2칸을 이동할 수 있다. 3칸? 4칸은? 또 거쳐서 가는 것이 훨 이득이다. 고로 가장 작은 단위 2개를 체크 한다.

---

MAX 함수.

max 함수를 이용해서 위로 가는 경우 / 아래로 가는 경우 다 계산.
0부터 계산을 할 것임.

만들어 놓은 행동에 의하면 체크 해야 하는 것은 현재 기준으로 두 칸 뒤에 까지 체크를 해야함.
n = 2 일때, 1, 0 의 값들 모두 체크 해야 하기 때문에.
1의 값을 미리 계산 해 둬야 한다.

	dp[0][0] = score[0][0]
    dp[1][0] = score[1][0]

    dp[0][1] = score[0][1] + dp[1][0]
    dp[1][1] = score[1][1] + dp[0][0]

그리고 계산.

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

그 후, dp를 사용하면 메모리 너무 잡아먹으니까. score 리스트만 이용하기.

    score[0][1] += score[1][0]
    score[1][1] += score[0][0]

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

import sys

T = int(sys.stdin.readline())
result = []

for i in range(T):
    n = int(sys.stdin.readline())
    score = []

    for j in range(2):
        data = list(map(int, sys.stdin.readline().split()))
        score.append(data)

    score[0][1] += score[1][0]
    score[1][1] += score[0][0]

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

    result.append(max(score[0][n - 1], score[1][n - 1]))

for i in result:
    print(i)