[백준] 9465번: 스티커

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

initial (correct)

As I have said, observing the pattern for DP is very important. It is very similar to https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-2579%EB%B2%88-%EA%B3%84%EB%8B%A8-%EC%98%A4%EB%A5%B4%EA%B8%B0
and especially this graph below made me rethink everything about DP.

(ref:https://daimhada.tistory.com/181)

Instead of trying to think ahead from the current step or stair or position, think where we came from previous position and ended up in current position. Then I tried finding out the pattern, espeically the bit where we skip the current column to get the bigger value at the next column.

The n==1, n==2 part in my drawing is wrong but you get the point. We need to consider previous 2 columns. Here we initialise dp[i][j] as the maximum value at column j at row i.

my correct solution:

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

don't forget to put

import sys
input = sys.stdin.readline

for faster reading.

complexity

The time complexity of your code is O(m) for each test case. This is because, in the worst case, you iterate over the array of size m to calculate the maximum values for each cell in the dynamic programming table.

The space complexity of your code is O(m) as well. You create a dynamic programming table with two rows, each of size m, to store intermediate results.

Overall, your code has a time complexity of O(m) and a space complexity of O(m) per test case. The time complexity is linear in the size of the input m, and the space complexity is also linear because of the dynamic programming table.