[python] 백준 9456 스티커

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

문제 해결

dp로 문제를 해결 해야할 것 같음

dp[0][n]을 n번째 열에는 스티커를 떼지 않고 얻을수 있는 점수 최대 값을 표현하고

dp[1][n]을 n번째 열에 1행 스티커를 땔 때 얻을 수 있는 점수 최댓값을 표현

dp[2][n]을 n번째 열에 2행 스티커를 땔 때 얻을 수 있는 점수 최댓값을 표현한다고 하고

코드를 짜면 쉽게 짤 수 있다.

 

code

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    board = [[0 for _ in range(n+1)]]
    for _ in range(2):
        board.append([0]+list(map(int, input().split())))
    dp = [[0 for _ in range(n+1)] for _ in range(3)]
    for i in range(1,n+1):
        dp[0][i] = max(dp[1][i-1], dp[2][i-1]) + board[0][i]
        dp[1][i] = max(dp[0][i-1], dp[2][i-1]) + board[1][i]
        dp[2][i] = max(dp[0][i-1], dp[1][i-1]) + board[2][i]
    ans = max(dp[0][n], dp[1][n], dp[2][n])
    print(ans)