DP(다이나믹 프로그래밍): 백준 13398 파이썬 연속합 2

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

13398번: 연속합 2

 

풀이:

1912번 연속합 문제에서 수를 하나 제거하는 경우가 추가된 문제이다. 

수를 제거한 경우와 제거하지 않은 경우를 나누어 dp 배열을 생성하고 큰 수를 비교하면서 저장해 나가면 된다.

항상 느끼는 거지만 다이나믹 프로그래밍 문제는 코드는 정말 간단하지만 문제의 규칙, 점화식을 생각해내는 과정이

너무 어렵다.

 

정답:

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

dp = [[0] * n for _ in range(2)]

# 수를 한 번 제거한 경우와 제거하지 않은 경우를 나눔
# 제거할 횟수가 남아있는 배열은 dp[1]에, 제거할 횟수가 남아 있지 않은 배열은 dp[0]에 저장
dp[0][0] = arr[0]
dp[1][0] = arr[0]

for i in range(1, n):
    # 그럼 dp[0][i]는 본인을 제거한 나머지의 합 dp[1][i-1과] 이전에 제거된 배열과 본인의 합 중 더 큰 값이 dp[0][i]이 된다.
    dp[0][i] = max(dp[1][i-1], dp[0][i-1] + arr[i])
    # dp[1][i]는 본인 혼자만의 합과 이전의 합 중 더 최대인 값을 고르면 된다.
    dp[1][i] = max(dp[1][i-1]+arr[i], arr[i])

result = -10001

for i in range(2):
    for j in range(n):
        if dp[i][j] > result:
            result = dp[i][j]


print(result)