문제
접근
DP 문제이다.
i번 째 열에서 할 수 있는 행동은 스티커를 선택하지 않거나, 첫 번째 행의 스티커를 선택하거나, 두 번째 행의 스티커를 선택할 수 있다.
이를 모두 확인하기 위하여 DP 배열은 n x 3으로 설정하였다.
DP(i, j) = i번째 열에서 j행의 스티커를 선택했을 때 최대 점수이다.
j행은 0, 1, 2로 이루어져있으며, 0은 아무거도 선택하지 않은 경우이다.
각 경우에 대해 생각해보자.
아무거도 선택하지 않은 경우는 i-1번째 열에서 어떤 선택을 하던 상관없다.
즉 DP(i-1)에서 최대값을 선택하면 된다.
1번 행의 스티커를 선택했다고 하면, i-1열에서는 아무거도 선택하지 않았거나, 2번 행의 스티커를 선택해야 한다.
즉 DP(i,1)은 (i,1)의 점수 + max(DP(i,0), DP(i,2)) 이다.
DP(i,2)역시 (i,2)의 점수 + max(DP(i,0), DP(i,1)) 이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
arr = [list(map(int, input().split())) for _ in range(2)]
dp = [[0]*(n+1) for _ in range(3)]
dp[1][0] = arr[0][0]
dp[2][0] = arr[1][0]
for i in range(1, n):
dp[0][i] = max(dp[0][i-1], dp[1][i-1], dp[2][i-1])
dp[1][i] = max(dp[0][i-1], dp[2][i-1]) + arr[0][i]
dp[2][i] = max(dp[0][i-1], dp[1][i-1]) + arr[1][i]
print(max(dp[0][n-1], dp[1][n-1], dp[2][n-1]))