[BOJ] 13398 연속합 2 (Python3)

문제

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보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

정답 코드

N = int(input())

numbers = list(map(int, input().split()))
dp = [[i for i in numbers] for _ in range(2)]

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

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

 10
 10 -4 3 1 5 6 -35 12 21 -1


[10, -4, 3, 1, 5, 6, -35, 12, 21, -1]
[10, -4, 3, 1, 5, 6, -35, 12, 21, -1]

[10, 6, 9, 10, 15, 21, -14, 12, 33, 32]
[10, 10, 13, 14, 19, 25, 21, 33, 54, 53]
54

문제 풀이

dp로 풀이하여 푸는 문제이다.

n 만큼의 배열을 두줄로 만들어서, 첫번째는 숫자를 제거하지 않은 경우, 두번째 줄은 숫자를 제거한 경우를 기록해준다.

숫자를 제거하지 않는 경우에는 첫번째 인덱스부터 누적합을 계산해가며, 만약 현재 인덱스의 숫자보다 누적합이 작으면 합을 중단하고 지금 인덱스의 숫자를 기록한다.

숫자를 제거하는 경우에는 이전 수와 지금 인덱스 숫자의 합이 이전의 합보다 작다면 현재 인덱스를 합하지 않는 경우가 더 큰 경우이므로, 숫자를 제거하지 않은 경우의 합에서 값을 가져와 자신을 제거한다.