[DP] boj.9465 스티커

문제 해석

이 문제는 단순히 생각하면 최대 합을 나타내는 경우의 수 또는 조합을 구하는 문제이다. 단순하게 우선 브루트포스가 가능한지 보기 위해서는 시간복잡도를 분석해보면 되는데, n개의 칸을 선택하는지 여부에 따라 대략적으로 O(2^n)이 될 것으로 보인다. 따라서 경우의 수를 뽑는다던지 하는 방식으로는 접근하기 어려울 것으로 보았다.

이 문제는 대표적으로 DP를 적용하는 문제이다. 다이나믹 프로그래밍은 대개 이전 데이터를 이후에 계속 사용하는 방식에서, 이를 효율적으로 다루기 위해 사용된다. 재귀 방식에도 적용할 수 있고, 이처럼 문제 해석상 앞에서 적용한 데이터를 계속 사용하는 경우에 적용 가능하다.

DP는 일반적으로 top-down 방식 또는 bottom-up 방식으로 적용되는데, 해당 문제에서는 bottom-up 방식으로 접근해야 한다.

풀이 코드

블록을 배열 칸으로 변수에 담은 뒤에, 왼쪽(bottom)에서 오른쪽으로 이동하면서(up) 각 칸에 누적된 합 값을 담으면 된다. 합을 담을 때 고려해야 하는 경우는 두 가지가 있다.

1. 바로 오른쪽 대각선 블록을 취함
2. 다음 블록의 대각선 블록을 취함

이를 이용하여 로직을 구성하면 아래와 같다.

import sys
input = sys.stdin.readline

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

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