[ 9465 ] [ DP ] 스티커

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

9465번: 스티커

 

풀이 과정

---

1. 2차원 DP 테이블을 구성한다.
   1. DP[i][0]: i번째 스티커를 붙이지 않았을 때 최대 점수
   2. DP[i][1]: i번째 스티커를 윗줄에 붙였을 때 최대 점수
   3. DP[i][2]: i번째 스티커를 아랫줄에 붙였을 때 최대 점수
2. 점화식을 구해준다.
   1. 예시로 DP[i][0]의 경우는 i번째 스티커를 붙이지 않을 때의 경우이므로 DP[i-1][0], DP[i-1][1], DP[i-1][2]중 최댓값과 같다.
   2. DP[i][1]이나 DP[i][2]를 구할 때는, 현재 스티커의 점수를 더해서 저장해주어야 한다.
3. 테이블을 모두 구성하면 DP 테이블의 맨 마지막 행의 최댓값을 구해서 출력시켜준다.

---

소스 코드 

---

import sys

input = lambda: sys.stdin.readline().rstrip()
T = int(input())

for _ in range(T):
    N = int(input())
    scoreA = list(map(int, input().split()))
    scoreB = list(map(int, input().split()))
    DP = [[0] * 3 for _ in range(N)]
    DP[0][0], DP[0][1], DP[0][2] = 0, scoreA[0], scoreB[0]
    for i in range(1, N):
        DP[i][0] = max(DP[i-1][0], DP[i-1][1], DP[i-1][2])
        DP[i][1] = max(DP[i-1][0], DP[i-1][2]) + scoreA[i]
        DP[i][2] = max(DP[i-1][0], DP[i-1][1]) + scoreB[i]

    print(max(DP[N-1]))