[알고리즘 문제풀이] 스티커

문제 제목 : 스티커

문제 난이도 : 하

문제 유형 : 동적 프로그래밍

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

문제풀이 아이디어

< 소스코드 >

test = int(input())

for i in range(test):
    s = []
    n = int(input())
    
    for j in range(2):
        s.append(list(map(int, input().split(' '))))
        
    for k in range(1, n):
        # 두번째 값까지는 대각선 값 더해주기
        if k  == 1:
            s[0][k] += s[1][k-1]
            s[1][k] += s[0][k-1]
        # 세번째 값부터 max(대각선, 대각선 왼쪽)
        else:
            s[0][k] += max(s[1][k-1], s[1][k-2])
            s[1][k] += max(s[0][k-1], s[0][k-2])
    print(max(s[0][n-1], s[1][n-1]))