#318 백준 파이썬 [9465] 스티커

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

 

SOLUTION

2개의 행 뿐이므로 i번째 열의 최댓값은 다음과 같다.

1) 다른 행, 바로 이전 열의 최댓값 + 현재 스티커

2) 다른 행, 2번째 전 열의 최댓값 + 현재 스티커

PYTHON CODE

T = int(input())
for _ in range(T):
    n = int(input())
    
    sticker = []
    sticker.append(list(map(int, input().split())))
    sticker.append(list(map(int, input().split())))
    
    max_sticker = [[0 for _ in range(n)] for _ in range(2)] #0번부터 차례대로 최대 값 저장
    max_sticker[0][0] = sticker[0][0]
    max_sticker[1][0] = sticker[1][0]
    
    
    for i in range(1, n):
        if i == 1:
            max_sticker[0][1] = sticker[1][0] + sticker[0][1]
            max_sticker[1][1] = sticker[0][0] + sticker[1][1]
        else:
        	#바로 이전대각선 방향이 최댓값일 경우 vs 2개 이전 대각선 방향이 최댓값일 경우
            max_sticker[0][i] = sticker[0][i] + max(max_sticker[1][i-2], max_sticker[1][i-1])
            max_sticker[1][i] = sticker[1][i] + max(max_sticker[0][i-2], max_sticker[0][i-1])
    print(max(max_sticker[0][n-1], max_sticker[1][n-1]))