[백준] 9465번 스티커 (by Python)

문제

제법 Dynamic Programming에 익숙해졌다고 생각했는데 점화식을 떠올리기가 힘들었던 문제. 메모이제이션 방법을 떠올렸지만 점화식의 형태를 구상하기가 힘들었다. 수열로 따졌을 때 새로 추가되는 column의 값들에 따라서 최댓값도 달라지기 때문에 그랬던 것 같다. 이 문제의 breakthrough는 크게 다음 2가지였던 것 같다.

① 새로운 값이 어떤 값이냐에 따라서 답이 달라진다면 다 대입해볼 것!

② 메모이제이션으로 해당 값까지의 최적 경로에 대한 축적을 한다는 것을 기억하고 무엇을 축적해야할지 생각할 것!

 

풀이

t = int(input())

for _ in range(t):
    n = int(input())
    arr = []
    ans = [[0] * n for _ in range(2)]
    for _ in range(2):
        arr.append(list(map(int, input().split())))
    for i in range(n):
        if i == 0:
            ans[0][0] = arr[0][0]
            ans[1][0] = arr[1][0]
        elif i == 1:
            ans[0][1] = arr[1][0] + arr[0][1]
            ans[1][1] = arr[0][0] + arr[1][1]
        else:
            ans[0][i] = arr[0][i] + max(ans[1][i - 1], ans[1][i - 2])
            ans[1][i] = arr[1][i] + max(ans[0][i - 1], ans[0][i - 2])
    print(max(ans[0][n - 1], ans[1][n - 1]))