스티커 (BOJ-9465)
‘시간제한 1초, 메모리제한 256MB, BOJ-9465’
스티커 (BOJ-9465)
이걸 dp로 떠올리기가 너무 어려웠다. 이 문제는 dp를 3가지로 나타내면 된다.
dp[n][0]: 스티커의 n열에서 윗 부분을 뗐을 경우 최대 점수.
dp[n][1]: 스티커의 n열에서 아랫 부분을 뗐을 경우 최대 점수.
dp[n][2]: 스티커의 n열에서 아무것도 떼지 않았을 경우 최대 점수.
dp가 항상 주어지는 데이터와 형태가 똑같다고 생각해서 이런 형태의 dp를 떠올리질 못했다;;
p에 각 스티커의 점수들이 배열로 저장되어 있다면, 첫번째 열의 dp는 다음과 같다.
dp[1][0] = p[0][0]
dp[1][1] = p[1][0]
dp[1][2] = 0
첫번째 열에선 뗀 스티커가 처음이므로 해당 스티커의 점수가 저장되면 된다.
둘다 떼지 않을 경우는 뗀 스티커가 없으므로 점수는 0이 된다.
두번째 열부터 dp에 모든 경우의 값을 저장하면 된다.
dp[i][0]: 윗 스티커를 뗄 경우 이전 열에서 아랫 스티커를 뗐거나 둘다 떼지 않은 경우이므로 이 두 경우의 최대 점수들 중에서 최댓값을 현재 스티커의 점수(p[0][i])에 더해서 dp[i][0]에 저장하면 된다.
dp[i][1]: 아랫 스티커를 뗄 경우 이전 열에서 윗 스티커를 뗐거나 둘다 떼지 않은 경우이므로 이 두 경우의 최대 점수들 중에서 최댓값을 현재 스티커의 점수(p[1][i])에 더해서 dp[i][1]에 저장하면 된다.
dp[i][2]: 현재 열의 스티커를 하나도 떼지 않을 경우 이전 열에서 윗 스티커를 뗐거나 아랫 스티커를 뗐거나 둘다 떼지 않은 경우이므로 이 세 경우의 최대 점수들 중에서 최댓값을 dp[i][2]에 저장하면 된다.
마지막엔 dp의 마지막 열에 모든 경우의 최댓값들이 저장되므로, 이 중에서 최댓값을 구하면 된다.
from sys import stdin
for _ in range(int(input())):
n = int(input())
p = []
dp = [[0] * 3 for _ in range(n + 1)]
for i in range(2):
p.append([0] + list(map(int, stdin.readline().rstrip().split())))
dp[1][0] = p[0][1]
dp[1][1] = p[1][1]
dp[1][2] = 0
for i in range(2, n + 1):
dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + p[0][i]
dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + p[1][i]
dp[i][2] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2])
print(max(dp[n]))
