[백준] #9465 스티커 (python)

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

문제 설계

하나를 고르면 인접한 상하좌우를 선택하지 못한다.

DP로 풀어야 함

 

[0][i] 번째를 골랐다면 이전에 [1][i-1] 이거나 [1][i-2] 둘 중 하나를 골랐을 거임.

예제를 보면 옆에 인접한 열에서 반드시 선택된다는 조건은 없다. 

 

행이 1개밖에 없는 경우에 주의하고

 

초기값 세팅

dp[0][0]=maps[0][0]

dp[1][0]=maps[1][0]

dp[0][1]=dp[1][0]+maps[0][1]

dp[1][1]=dp[0][0]+maps[1][1]

 

문제 풀이

n=int(input())

for _ in range(n):
    c=int(input())

    maps=[]
    dp=[[0]*c for _ in range(2)]
    for _ in range(2):
        maps.append(list(map(int,input().split())))
    if c==1:
        print(max(maps[0][0],maps[1][0]))
        continue

    dp[0][0]=maps[0][0]
    dp[1][0]=maps[1][0]

    dp[0][1]=dp[1][0]+maps[0][1]
    dp[1][1]=dp[0][0]+maps[1][1]


    for i in range(2,c):        
        dp[0][i]=maps[0][i]+max(dp[1][i-1],dp[1][i-2])
        dp[1][i]=maps[1][i]+max(dp[0][i-1],dp[0][i-2])
    
    
    print(max(dp[0][c-1],dp[1][c-1]))