[백준] 13398. 연속합 2(Python, 파이썬)
백준 온라인의 문제 풀이입니다.
📖 [백준] 13398. 연속합 2
| 시간 제한 | 메모리 제한 | 난이도 |
|---|---|---|
| 2초 | 512 MB | 골드 5 |
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보다 작거나 같은 정수이다.
✔️ 출력
첫째 줄에 답을 출력한다.
✔️ 입력 출력 예시
| 입력 | 출력 |
|---|---|
| 10 10 -4 3 1 5 6 -35 12 21 -1 | 54 |
🗒️ 내 풀이
입력 값의 범위가 100,000까지이기 때문에 값을 하나씩 빼보면서 모든 경우를 살펴보면 $O(N^2)$으로 시간초과가 발생할 것이다. 따라서 다이나믹 프로그래밍으로 실행속도를 줄여야 한다.
해당 문제는 값을 제거하지 않았을 때와, 제거했을 때를 따로 살펴봐야 한다.
dp[0][i]는 값을 제거하지 않았을 때, i번 째 값까지의 연속합 중 최대값이고, dp[1][i]는 값을 제거했을 때의 최대값이라고 하자.
먼저 값을 제거하지 않았을 때를 살펴보자. i번 째 값을 더했을 경우, i - 1 번째 까지의 합 + i번째 값과 i번째 값 중 큰 값이 최대값이 된다.
따라서, 점화식은 다음과 같다.
dp[0][i] = max(data[i], dp[0][i - 1] + data[i])
다음으로 1개를 제거한 경우를 살펴보자. 이때는 두 가지 경우가 있다.
- i번 째를 제거한 경우 :
dp[1][i] = dp[0][i - 1] - 앞에서 이미 제거한 경우 :
dp[1][i] = dp[1][i - 1] + data[i]
i번 째를 제거한 경우는 단순히 i - 1번 째의 제거하지 않은 연속합 최대값을 가져오면 된다. 따라서 점화식은 다음과 같다.
dp[1][i] = dp[0][i - 1]
앞에서 이미 제거한 경우는, i - 1번 째까지 중 제거한 경우의 연속합 최댓값에 i번 째 값을 더한 경우가 최대값이 된다. 따라서 점화식은 다음과 같다.
dp[1][i] = dp[1][i - 1] + data[i]
그래서 1개를 제거한 경우는 두 가지 경우 중 큰 값을 가져오면 되므로 최종적으로 점화식은 다음과 같다.
\[\begin{align} \text{제거하지 않은 경우 : }dp[0][i] = max(data[i], dp[0][i - 1] + data[i])\\ \text{값을 1개 제거한 경우 : }dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + data[i]) \end{align}\]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
import copy
input = sys.stdin.readline
n = int(input())
data = list(map(int, input().split()))
dp = [copy.deepcopy(data), copy.deepcopy(data)]
# 일반 연속합 점화식 : dp[0][i] = max(data[i], dp[0][i - 1] + data[i])
# 1개를 제외한 경우
# - i번 째를 제거한 경우 : dp[1][i] = dp[0][i - 1]
# - 앞에서 이미 제거한 경우 : dp[1][i] = dp[1][i - 1] + data[i]
# => dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + data[i])
for i in range(1, n):
dp[0][i] = max(data[i], dp[0][i - 1] + data[i])
dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + data[i])
print(max(max(dp[0]), max(dp[1])))
