[Python] 스티커 - 백준 (DP)

해당 글은 백준 9465번 문제 '스티커'를 다룬다.

문제

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

9465번: 스티커

 

설명

해당 문제는 동적 계획법으로 푸는 문제로, 임의의 한 스티커를 선택했을 때 경우의 수는 2개가 있다.

선택한 스티커의 왼쪽에 대각선(↘)을 고르기 or 한칸을 건너뛰고 대각선에 있는 값을 선택하는 경우이다.

(단, 선택한 스티커의 상하좌우 제외)

이를 이용해서 스티커의 왼쪽에서 오른쪽으로 갈수록 DP를 최댓값으로 업데이트 시켜준다.

최종 출력값은 스티커의 가장 오른쪽의 1, 2행 중에 최댓값이다.

 

코드

t = int(input())

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

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

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