https://www.acmicpc.net/problem/9465
9465번: 스티커첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의www.acmicpc.net
이번엔 세로로 dp를 돌려봤다.
dp[0][i]=i번째의 위에 있는 스티커를 뗄 때의 최댓값
dp[0][i]=i번째의 아래 있는 스티커를 뗄 때의 최댓값
여기서 dp[0][i]를 뗄러면 dp[1][i-1]의 스티커를 뗐거나, dp[?][j-1]을 아예안 똈거나 둘 중하나이다.
그럼 dp[?][i-2]의 최댓값과, dp[1][i-1]을 비교하여 이중 최댓값에 스티커의 값을 더해주면 된다.
그런데 생각을 해보자
만일 우리가 dp[0][i-2]를 뗐다면, 당연히 dp[1][i-1]을 떼고 그다음 dp[0][i]를 뗐을 것이다.
dp[1][i-1]이 음수가 아닌 이상 이 값은 당연히 dp[0][i-2]보다 크므로,
실질적으로 dp[1][i-1]과 dp[1][i-2]의 값중 큰 값만 비교하면 된다.
이를 점화식으로 정리하면
dp[0][i]=max(dp[1][i-1],dp[1][i-2])+ dp[0][i](해당 스티커값)
dp[0][i]=max(dp[0][i-1],dp[0][i-2])+ dp[1][i](해당 스티커값)
이 된다.
코드
처음에는 스티커의 가격과 dp배열을 따로 구성했으나, 다른 풀이를 보고 깔끔하게 바꿨다.
첫 풀이
t=int(input())for _ in range(t): n=int(input()) sticker=[]
sticker.append([0]+(list(map(int,input().split()))))
sticker.append([0]+(list(map(int,input().split()))))
dp=[[0,0] for _ in range(n+1)] dp[1]=[sticker[0][1],sticker[1][1]]
#dp[i][j]는 j로 끝났을때 점수의 최댓값 for i in range(2,len(dp)):
dp[i][0]=max(dp[i-1][1],max(dp[i-2]))+sticker[0][i]
dp[i][1]=max(dp[i-1][0],max(dp[i-2]))+sticker[1][i]
print(max(dp[n]))깔끔한 풀이
for _ in range(int(input())): n=int(input())
dp=[[0]+[* map(int,input().split())] for _ in range(2)]
for i in range(2,n+1): max_0=max(dp[1][i-1],dp[1][i-2])
max_1=max(dp[0][i-1],dp[0][i-2]) dp[0][i]+=max_0
dp[1][i]+=max_1 print(max(dp[0][n],dp[1][n]))