스티커

백준 9465번: 스티커

아이디어

간단한 dp 문제다. 스티커가 두 줄이기 때문에 dp테이블도 두 줄로 만들었다. 테이블에는 "해당 위치에 있는 스티커를 선택했을 때 만들 수 있는 최대한의 점수"를 기록했다.

코드

import sys
input = sys.stdin.readline

T = int(input())
while T > 0:
    n = int(input())
    sticker = [list(map(int, input().split())) for _ in range(2)]
    dp = [[0] * n for _ in range(2)]

    dp[0][0] = sticker[0][0]
    dp[1][0] = sticker[1][0]
    
    if n > 1:
        dp[0][1] = sticker[1][0] + sticker[0][1]
        dp[1][1] = sticker[0][0] + sticker[1][1]

    if n > 2:
        for i in range(2, n):
            dp[0][i] = max(dp[1][i - 2], dp[1][i - 1]) + sticker[0][i]
            dp[1][i] = max(dp[0][i - 2], dp[0][i - 1]) + sticker[1][i]
            
    m1 = max(dp[0])
    m2 = max(dp[1])
    print(max(m1, m2))

    T -= 1

여담

아 클래스4 언제다풀지