백준(9465) - 스티커 Python

백준(9465) - 스티커

문제풀이: 다이나믹 프로그래밍, 파이썬

문제를 읽고 규칙을 찾아내면 쉽게 풀 수 있다.

1. 1 * 2 배열이면 그냥 자기 위 아래 중 큰값을 찾으면 된다.

2. 

   2 * 2 배열인 경우

   ​ (i,j) 의 값은 (i+1,j-1)를 더한 값과 같다.

   ​ (i+1,j) 의 값은 (i,j-1)를 더한 값과 같다.

​ (i,j) 의 값은 (i+1,j-1)과 (i+1,j-2) 중 큰값과 더한 값이다.

​ (i+1,j) 의 값은 (i,j-1)과 (i,j-2) 중 큰값과 더한 값이다.

1. n만큼 비교후 위와 아래값중 더 큰 값을 출력하면 된다.

import sys
input = sys.stdin.readline

testcase = int(input())

for _ in range(testcase):
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(2)]
    answer = 0
    for i in range(n):
        if i - 2 >= 0:
            arr[0][i] += max(arr[1][i-1], arr[1][i-2])
            arr[1][i] += max(arr[0][i-1], arr[0][i-2])
        elif i - 1 >= 0:
            arr[0][i] += arr[1][i-1]
            arr[1][i] += arr[0][i-1]
    
    print(max(arr[0][-1], arr[1][-1]))