[DP] boj 9465 - 2행 배열에서 점화식 구하기

백준 9465는 이제까지의 dp 문제와 조금 다르게 입력값이 2행으로 존재하는 배열이다.

초기화할 때 1차원 리스트는 dp = [0] * n 이렇게 하면 되는데, 2행짜리 2차원 리스트는

dp = [ [0] * n ] * 2 또는 dp = [ [0] * n for _ in range(2) ] 형태로 만들어야 된다.

 

여기서 속도를 더 높이려면 함수화하거나 참고 링크처럼 dp를 따로 선언하지 않고 입력 배열에 더해나가야 될 것 같다.

import sys

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    matrix = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(2)]
    dp = [[0] * n for _ in range(2)]

    dp[0][0] = matrix[0][0]
    dp[1][0] = matrix[1][0]
    dp[0][1] = matrix[0][1] + dp[1][0]
    dp[1][1] = matrix[1][1] + dp[0][0]

    for i in range(2, n):
        dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + matrix[0][i]
        dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + matrix[1][i]

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