[백준] 13398번 : 연속합 2

13398번: 연속합 2

13398번: 연속합 2

🤔 문제분석

dp 테이블을 2개로 나누어 문제를 해결한다. 하나라도 빠지지않는 테이블과 그렇지 않는 테이블을 나눈다.

하나라도 빠지는 테이블을 구할때에는 이전에 하나라도 빠진 테이블에서의 최대값과, 현재 값을 제외한 누적합 중의 최대값을 선택하면 최대 하나가 빠지는 값의 최대 누적합을 구할 수 있다.

점화식은 아래와 같이 표현 할 수 있습니다. dp[0] 테이블은 일반적인 누적합의 최대값이고 dp[1] 테이블이 최대 하나가 빠지는 누적합 테이블이다.

dp[0][i] = max(dp[0][i-1] + arr[i], dp[0][i])
dp[1][i] = max(dp[0][i-1], dp[1][i-1] + arr[i])

💻 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [[a for a in arr] for _ in range(2)]

for i in range(1, n):
    dp[0][i] = max(dp[0][i-1] + arr[i], dp[0][i])
    dp[1][i] = max(dp[0][i-1], dp[1][i-1] + arr[i])
    
print(max(max(dp[0]), max(dp[1])))

🎯 피드백 및 개선사항

다이나믹 프로그래밍의 유형 중 한가지를 익힐 수 있는시간이었다.