[BOJ] 13398번 - 연속합 2

---

문제설명

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

13398번: 연속합 2

사고과정

• 1차원 리스트 DP 테이블로 풀려고 하니 시간초과가 발생했다. 2차원 리스트를 사용해야 하는데 어떻게 사용할지 아이디어가 떠오르지 않았다..
• 풀이를 보니, 문제에거 1개의 원소만 삭제할 수 있다고 했으니 DP 테이블을 2차원으로 두되, 첫 번째 행의 DP 테이블은 1개의 원소를 제거할 여지가 남아있는 경우, 두 번째 행은 제거하지 않고 그대로 갈 경우로 두고 진행했다. 그리고 DP 테이블의 열은 주어진 수열 원소 순서대로 하며 의미는 "해당 원소값이 제거될 때와 제거되지 않을 때"를 의미한다고 보면 된다.

	10	-4	3	1	...
1개의 원소가 제거될 때의 DP( A )	10	-4를 제거할 경우 = 이전 열의 B 값 & -4를 제거하지 않을 경우 = 이전 열의 A + -4  중 max 값
제거하지 않고 그대로 갈 경우의 DP( B )	10	-4 원소까지 더할 경우 & -4 원소 더하지 않고 이전 열의 B값 중 max 값

 

위 표의 설명을 보면 알 수 있다. 따라서 점화식을 세우면 다음과 같다. 우선 A에 대한 점화식을 세우면 아래와 같다. $$DP[0][j] = max(DP[1][j-1], DP[0][j-1] + array[j])$$

B에 대한 점화식은 아래와 같다. 저번에 풀어본 연속합 문제와 동일한 점화식으로 구현하면 된다. $$DP[1][j] = max(DP[1][j-1] + array[j] , array[j])$$

풀이(스스로 못 푼 풀이)

import sys
input = sys.stdin.readline

n = int(input())
array = list(map(int, input().split()))
# DP를 2차원 리스트 -> 행이 0인 리스트는 1개를 제거한 후의 DP, 행이 1인 리스트는 아무것도 제거하지 않은 수열 상태의 DP
dp = [[0] * n for _ in range(2)]
dp[0][0] = dp[1][0] = array[0]

for i in range(2):
    for j in range(1, n):
        # 1개 제거할 경우
        dp[0][j] = max(dp[1][j-1], dp[0][j-1] + array[j])
        # 그냥 그대로 갈 경우
        dp[1][j] = max(dp[1][j-1] + array[j], array[j])

res = max(max(dp[0]), max(dp[1]))
print(res)