[알고리즘/파이썬] 백준 9465 - 스티커

문제

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

9465번: 스티커

 

풀이

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ대체 8달 전에 무슨 일이...? ;;;;;;;;;

 

DP 대표 문제~. 실버1이지만 볼때마다 뭔가 생각이 바로 떠올리지 않는 것 같다. ㅎㅎ -1의 대각선 , -2의 대각선 중에 큰 숫자를 지금의 스티커 점수와 더해주면 된다. 저렇게 고르면 자연스럽게 서로 인접한 스티커끼리는 더하지 않게 돼있다. 

 

코드

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