[BOJ] 스티커

---

코드

import sys
input = sys.stdin.readline

def solution(arr, n):
    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[0][i-2], arr[1][i-2])
            arr[1][i] += max(arr[0][i-1], arr[0][i-2], arr[1][i-2])

    return max(map(max, arr))

arr = []

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

결과

풀이 방법

• 다이나믹 프로그래밍을 활용하였다.
• 현재 스티커를 뗀다고 가정하면 이전에 바로 왼쪽 스티커는 뗄 수 없었을 것이다.
• 따라서 왼쪽 대각선 방향의 스티커를 떼거나, 떼지 않을 수도 있으므로, 이전 스티커들의 합은 왼쪽 대각선 방향 스티커와 그 이전 열(i-2열)의 두 스티커 중 큰 값을 선택하면 된다
• 이렇게 n열까지 차례로 스티커 합의 최대값을 더하였다.

---