[BOJ] 9465. 스티커 (🥈, DP)

🔗

풀이

2n 개의 스티커에 대해 구할 수 있는 최대 점수를 구하는 방법을 찾아야 한다. 최대 길이가 10만이기 때문에 브루트포스나 완전 탐색은 어려울 것 같다.

만약 길이가 1인 경우라고 생각하면 계산할 것도 없이 값 2개 중 큰 값을 고르면 된다.

만약 길이가 2라면, 서로 떼어지지 않도록 바로 양 옆에 붙은 값은 고를 수 없다. 파란색 화살표를 따라 변하는 경우와 빨간색 화살표를 따라 변하는 경우 2가지가 존재할 수 있다.

만약 길이가 3을 넘어가게 된다면 조금 달라진다.

길이가 2일 때처럼, 빨간색과 파란색 화살표로 구분해서 가는 길은 동일한다. 그러나 아래와 같은 경우를 추가로 고려해야 한다. 30에서 10을 거치지 않고 바로 100으로 오는 경우가 있을 수 있다. 10을 거치면 100의 바로 옆 칸이라서 떼어낼 수 없지만 30에서 바로 오게 되면 옆 칸이 아니기 때문에 떼어낼 수 있다.

길이가 4를 넘어가게 되면 특별히 추가로 더 고려해야 할 부분은 없다. 길이가 3일때와 동일한 부분만 고려하면 된다.

# 스티커

def sol(n, dp):
    if n > 1:
        dp[0][1] += dp[1][0]
        dp[1][1] += dp[0][0]!
        
        if n > 2:
            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])
    
    return max(dp[0][-1], dp[1][-1])
    
for _ in range(int(input())):
    n = int(input())
    dp = [list(map(int, input().split())) for _ in range(2)]
    print(sol(n, dp))