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

https://www.acmicpc.net/status?from_mine=1&problem_id=9465&user_id=wnsghk1025

채점 현황

t = int(input())
for _ in range(t):
    n = int(input())
    graph = [list(map(int, input().split())) for _ in range(2)]
    answer = [[0] * n for _ in range(2)]
    answer[0][0], answer[1][0] = graph[0][0], graph[1][0]
    ans = max(answer[0][0], answer[1][0])
 
    for i in range(1, n):
        for j in range(2):
            if i >= 2:
                answer[j][i] = graph[j][i] + max(answer[(j + 1) % 2][i - 1], answer[0][i - 2], answer[1][i - 2])
            else:
                answer[j][i] = graph[j][i] + answer[(j + 1) % 2][i - 1]
            ans = max(ans, answer[j][i])
    print(ans)

dp로 풀면 된다.

[a][b]에 있는 스티커를 뗀다고 가정했을 경우, 최대 점수는

[a][b]의 점수 + max(이전 열의 대각선 방향에 있는 스티커까지의 최대 점수, 2개 전 열에 있는 스티커를 선택했을 경우 최대 점수)이다.