[백준] 연속합 2

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

13398번: 연속합 2

1. 문제이해

수열에서 연속된 수를 선택해서 얻을 수 있는 가장 큰 합을 구하는 문제입니다. 무조건 하나의 수는 선택해야하고 하나의 숫자를 제거한 다음 연속된 수를 선택할 수 있습니다.

2. 문제접근

DP 방식으로 접근해 보았습니다.

dp[0][i]: 숫자를 삭제하지 않은 경우

dp[1][i]: 숫자를 한개 삭제한 경우로 나누어서 풀이하면 됩니다. 

점화식은 다음과 같습니다. 

dp[0][i] = max(dp[0][i - 1] + nums[i], nums[i]) : 숫자를 한개도 삭제하지 않는 경우에는 이어져 오는 숫자에 현재 숫자를 더한 것과 현재 숫자부터 시작하는 것이 더 나은지를 택해주면 됩니다.

dp[1][i] = max(dp[1][i - 1] + nums[i], dp[0][i - 1]) : 숫자를 한개 삭제하는 경우에는 이미 삭제되어 온 수열에 자신을 더한 것과 현재 숫자를 삭제했을 때를 비교하여 더 큰 수를 택해주면 됩니다.

3. 풀이

import sys

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())
nums = [0] + list(map(int, input().split()))

if n == 1:
    print(nums[1])
    sys.exit(0)

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

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

print(max(max(dp[0][1:]), max(dp[1][2:])))

정답을 구할 때 dp[1] (숫자를 한개 삭제한 경우)의 인덱스 2부터 선택한 이유는 맨 처음 숫자는 이어져오는 숫자도 없고 현재 숫자를 삭제한 경우이기 때문에 무조건 숫자 하나는 선택해야한다는 조건을 만족할 수 없기에 빼주었습니다.

4. 회고

골드5라도 DP는 어렵다..