문제

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

나의 코드 (답안 참고)

"""
1. 아이디어

2. 시간복잡도
O(N-2)정도? n이 2이상일때
"""

from sys import stdin
input = stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())

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

    # n = 1 인 경우
    if n == 1:
        print(max(dp[0][n-1], dp[1][n-1]))
        continue

    # n = 2 이상인 경우
    dp[0][1] += dp[1][0]
    dp[1][1] += dp[0][0]

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

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

    

느낀점

• n이 1일 경우
  스티커 2개가 인접해 있으므로 둘 중 높은 점수를 출력하면 된다.

• n이 2일 경우
  

마지막 인덱스 1의 입장에서 봤을 때 빨간 체크를 더한 값 또는 파란 체크를 더한 값 중 높은 점수를 출력한다.

• n이 3이상일 경우

마지막 인덱스 2의 입장에서 봤을 때 빨간 표시 두 개 중 하나를 더한 값 또는 파란 표시 두 개 중 하나를 더한 값 중 높은 점수를 출력한다.

이 때 인덱스 1에 있는 값은 n이 2일 경우의 과정을 한 상태의 값이 들어있다.

위와 같이 n이 2 이상일 경우 마지막 인덱스 n은

다른 줄의 인덱스 n-1 또는 n-2의 값 중 큰 값이 후보가 됨을 알 수 있다.

참고자료

https://ye333.tistory.com/entry/%EB%B0%B1%EC%A4%80python-9465%EB%B2%88-%EC%8A%A4%ED%8B%B0%EC%BB%A4