[BOJ 9465] 스티커 (Python3)

www.acmicpc.net/problem/9465

9465번: 스티커

 

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

 

이것 역시 DP 문제. 오늘은 DP party!!(하삼 따라해봄 ㅎㅎ)

여기서 내가 고안해낸 점화식은

dp[0][i]=max(dp[1][i-1], max(dp[0][i-2], dp[1][i-2]))+array[0][i]

dp[1][i]=max(dp[0][i-1], max(dp[0][i-2], dp[1][i-2]))+array[1][i]

이다. 바로 max(전에 꺼+자기 꺼, 전전꺼+자기꺼) 를 나타낸다.

여기서 나는 전전꺼를 선택할 때 0행에 있는 것을 선택하든 1행에 있는 것을 선택하든 큰 걸 선택하도록 했는데.. 사실 이렇게 안해도 

1행에 있는 현재 값을 선택할 때 0행에 있는 전전값을 선택해야 하는 것이 바른 점화식이다. 즉 이렇게!!

dp[0][i] = max(dp[1][i-1], dpdp[1][i-2]) + arr[0][i]
dp[1][i] = max(dp[0][i-1], dpdp[0][i-2]) arr[1][i]

 

왜냐하면 1행에 있는 현재 값+1행에 있는 전전값 선택해봤자 .. 1행에 있는 전전값+0행에 있는 전값+1행에 있는 현재값 이 조합이 더 클 수 밖에 없으므로. 이렇게 바꿔주는게 계산 시간을 줄이는데 용이한 점화식이 된다.