[백준] 9465-스티커

문제바로가기

def max_sticker(n, sticker):
    if n ==1:
        return max(sticker[0][0], sticker[1][0])
    dp = [[0]*(n) for _ in range(2)]
    
    dp[0][0] = sticker[0][0]
    dp[1][0] = sticker[1][0]
    dp[0][1] = dp[1][0] + sticker[0][1]
    dp[1][1] = dp[0][0] + sticker[1][1]
    
    for i in range(2, n):
        dp[0][i] = sticker[0][i] + max(dp[1][i-1], dp[1][i-2])
        dp[1][i] = sticker[1][i] + max(dp[0][i-1], dp[0][i-2])
    return max(dp[0][-1], dp[1][-1])
T = int(input())
for _ in range(T):
    n = int(input())
    matrix = [0]*2
    for i in range(2):
        matrix[i] = list(map(int, input().split()))
    print(max_sticker(n, matrix))

처음에는 matrix는 2행으로 했는데 dp를 1행으로 해서 반례가 계속 생겼다. 지피티한테 물어서 dp 1행으로는 완벽히 문제를 커버할 수 없단 걸 알게되고 결국 수정했다.