[백준] 9465 - 스티커

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

9465번: 스티커

문제 한줄 이해

-2행 n열의 스티커가 있고 스티커의 점수가 있을때 주어진 조건에 맞춰서 높은 점수를 확보하도록 스티커를 떼기

 

생각난 풀이

1번째 방법: DP가 떠올라서 점화식을 어떻게 세울까 고민했다. 

먼저 스티커를 골라갈때 2가지 경우가 있다. 지그재그로 갈건지 바로 다음칸은 뜯지 않고 다다음칸에 더 큰 점수를 갖는 스티커를 뜯을지이다.

그렇다면 DP에 어떤값을 저장하고 어떻게 활용하면 좋을까를 생각했을때

현재 내가 스티커를 고를건데 이전에 저장된 DP에 어떤 위치를 골랐을때의 값이 저장 시켜 이를 활용하면 된다고 생각했다.

이와 같이 현재 위치에서 스티커를 뽑을때 이전의 DP값중에서 대각선으로 오게 만들면 규칙을 적용하면서 값을 구해낼수 있다.

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

for _ in range(t):
    n = int(sys.stdin.readline())
    stiker = []
    for i in range(2):
        stiker.append(list(map(int,sys.stdin.readline().split())))    
    
    dp = [[0 for i in range(n+1)] for i in range(2)]
    dp[0][1] = stiker[0][0]
    dp[1][1] = stiker[1][0]
    
    for i in range(2,n+1):
        dp[0][i] = max(dp[1][i-2],dp[1][i-1])+stiker[0][i-1]
        dp[1][i] = max(dp[0][i-2],dp[0][i-1])+stiker[1][i-1]
    print(max(dp[0][n],dp[1][n]))