[Python] 백준 9456 - 스티커

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

9465번: 스티커

 

DP 문제다.

 

아래의 점화식을 통해 풀 수 있는 문제다.

dp[현재위치] += max(대각선 한 칸 뒤,  대각선 두 칸 뒤) 

 

처음에는 아래와 같이 풀고 맞았겠거니 했는데 99%에서 틀렸다.

t = int(input())
for _ in range(t):
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(2)]
    dp = [[0 for _ in range(n)] for _ in range(2)]
    dp[0][0] = arr[0][0]
    dp[1][0] = arr[1][0]

    for i in range(1,n):
        dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + arr[0][i]
        dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + arr[1][i]

    print(max(dp[0][-1], dp[1][-1]))

뭐가 잘못된건지 몰라서 한참 고민하다가 n=2일 때 틀린다는 것을 알았다. 

반례 
1
1
10 20
20 30

answer: 40
output: 70

모든 경우의 수를 생각하지 않아서 틀린거니... 역시 한번에 맞기가 힘들다.

아래 코드는 정답 코드.

t = int(input())
for _ in range(t):
    n = int(input())
    arr = [[0]+list(map(int,input().split())) for _ in range(2)]
    dp = [[0 for _ in range(n+1)] for _ in range(2)]
    dp[0][1] = arr[0][1]
    dp[1][1] = arr[1][1]

    for i in range(2,n+1):
        dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + arr[0][i]
        dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + arr[1][i]

    print(max(dp[0][-1], dp[1][-1]))