[BOJ] 9465번 - 스티커

---

문제설명

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

9465번: 스티커

사고과정

• 스티커가 좌우에 인접해서 떨어지기 때문에 같은 선분은 공유해선 안된다. 따라서 N = 1일 때까지는 바로 직전의 대각선 스티커와 더하되 N = 2번째 일 때부터는 바로 직전의 대각선을 더할 것인지 2칸 이전의 대각선을 더할 것인지 중에 최댓값을 선택하면 된다.
• 처음에 점화식을 잘 세웠다고 생각했는데, 에러가 발생했다.. 그래서 오히려 이상한 사고의 길로 들어섰다...풀이를 보니 처음에 생각했던 점화식이 맞았다.. 아마  행이 0일때, 1일 때 구분해서 점화식을 세울 때 실수를 했나보다.. 아쉽다..

풀이(스스로 못 푼 풀이)

import sys
input = sys.stdin.readline

for tc in range(int(input())):
    n = int(input())
    dp = []
    for _ in range(2):
        dp.append(list(map(int, input().split())))

    for j in range(1, n):
        if j == 1:
            dp[0][j] += dp[1][j-1]
            dp[1][j] += dp[0][j-1]
        else:
            dp[0][j] += max(dp[1][j-1], dp[1][j-2])
            dp[1][j] += max(dp[0][j-1], dp[0][j-2])

    res = max(dp[0][n-1], dp[1][n-1])
    print(res)