[백준] 13398번 연속합 2 - Python / 알고리즘 기초 1/2 - 다이나믹 프로그래밍 1 (연습)

ByungJik_Oh·2025년 4월 2일

[Baekjoon Online Judge]

목록 보기

65/244

💡 문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

💭 접근

1912번 연속합 문제와 비슷한 문제로, 누적합의 최대를 구하는 문제이지만 수를 하나 뛰어 넘을 수 있다는 조건이 하나 더 추가되었다.

이를 위해 각 원소마다의 누적합을 저장할 list는 2개가 필요하다. tmp에는 기본적인 누적합을 저장하고, dp에는 하나를 뛰어넘는 누적합을 저장한다.

그러면, dp를 갱신할 때 고려해야 비교해야할 것이 3가지가 있다.

입력 a의 i번째 원소 (a[i]) : tmp, dp 모두 직전값(tmp[i - 1], dp[i - 1])에 a[i]를 더한 값이 a[i]보다 작게 될 수 있다.
tmp의 직전 원소 (tmp[i - 1]) : 이는 a[i]를 뛰어 넘는 것을 의미하며, 주로 음수값이 들어있어 값이 작아질 경우 tmp[i - 1]로 저장해준다.
dp의 직전 값에 a의 현재 값을 더한 값 (dp[i - 1] + a[i]) : 이는 a[i]를 뛰어넘지 않고 더한 값이다.

ex) 예제 a = [10 -4, 3, 1, 5, 6, -35, 12, 21, -1]
i = 0, a[0] = 10
tmp = [10, ...]
dp = [10, ...]

i = 1, a[1] = -4 뛰어넘기
tmp = [10, 6, ...]
dp = [10, 10, ...]
$\vdots$
i = 6, a[6] = -35 뛰어넘기
tmp = [10, 6, 9, 10, 15, 21, -14, ...]
dp = [10, 10, 13, 14, 19, 25, 21, ...]

i = 7, a[7] = 12
tmp = [10, 6, 9, 10, 15, 21, -14, 12, ...]
dp = [10, 10, 13, 14, 19, 25, 21, 33, ...]
$\vdots$

따라서 점화식은 다음과 같이 도출할 수 있다.

tmp[i] = max(a[i], tmp[i - 1] + a[i])
dp[i] = max(tmp[i - 1], dp[i - 1] + a[i], a[i])

📒 코드

n = int(input())
a = list(map(int, input().split()))
tmp = [a[i] for i in range(n)]
dp = [a[i] for i in range(n)]

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

print(max(dp))