백준(Baekjoon) 13398번 : 연속합 2 - python 풀이

🔴 문제 개요

문제 원문 : 백준 온라인 저지(Baekjoon Online Judge)

🚀 난이도 : GOLD 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보다 작거나 같은 정수이다.

🟠 Solution

연속합 문제의 응용문제입니다. n의 범위가 10만까지 주어지기 때문에, 완전 탐색으로는 풀이가 불가능하고, 메모이제이션을 활용하는 dp 방법론으로 풀이가 가능합니다.

연속합 문제 리마인드

기본 연속합 문제를 간단하게 짚고 넘어가면, 이 문제에서 수를 제거하는 것을 고려하지 않아도 되는 문제입니다. 따라서, 선택지는 아래 두 경우 중 더 큰 경우만 고려하면 됩니다.

• 현재 원소 + 이전 원소까지의 결과를 포함
• 현재 원소부터 다시 시작

따라서 dp 테이블에서 dp[i]는 i번째 원소까지 포함했을 때 최대 연속 합으로 나타낼 수 있습니다.

n = int(input().rstrip())
nums = map(int, input().rstrip().split())
dp = list(nums)
for i in range(1, n+1):
	dp[i] = max(dp[i-1]+nums[i], nums[i])

하나의 수를 제거하는 것을 고려하기

이제 연속합 2문제에서는 하나의 추가 조건인 하나의 수를 제거할 수 있는 것을 고려해야 합니다. 비교적 간단한 구현에 비해 생각하기 매우 까다롭습니다. dp 문제가 다 그렇죠 뭐..

바로 dp 테이블을 2차원으로 설계하여, dp[0]은 수를 제거하지 않은 경우, dp[1]은 수를 제거한 경우 로 나타내는 것입니다. 이렇게 두면 dp[1]에서 먼저 제거한 수가 있고, 새로운 수를 제거하는 것이 더 최대값으로 나타낼 수 있을 때 dp[0]을 참조해서 제거하는 수를 업데이트 할 수 있습니다. 예시를 보겠습니다.

위와 같이 dp테이블을 초기화 한 후, 최소 하나의 수를 포함해야 하므로 첫 번째 원소를 포함했습니다.

dp[0][i]는 i번째 원소까지 포함했을 때 최대 값입니다. 따라서 dp[0][i] = max(dp[0][i-1]+nums[i], nums[i]) 이므로 dp[0][1]은 6이 됩니다.

반면, dp[1]은 하나의 원소를 제거할 수 있습니다. 따라서 dp[1][1]은 -4를 고려하지 않아도 되므로 10입니다. 이를 다음 음수가 나올때 까지 이어서 진행해보겠습니다.

이론상 위와 같은 경우에서 dp[1]은 -35를 고려하면 안됩니다. 하지만 이미 -4를 이전에 제외해버렸습니다. 이때 dp[0]을 참조하는 것입니다. dp[0]은 수를 하나도 제외하지 않는 경우이기 때문입니다. 따라서 dp[1]은,

• 이전에 제외한 -4를 계속 제거하는 경우인 $dp[1][i-1]+nums[i]$
• 이전에 제외한 -4를 다시 포함하고 nums[i]를 새롭게 제거하는 경우인 $dp[0][i-1]$

중 더 큰 경우의 값을 가져가면 됩니다.

즉, $dp[1][i] = max(dp[1][i-1] + nums[i], dp[0][i-1])$ 입니다.

위 예시를 계속 이어서 작성해보면 아래와 같습니다.

주의할 점은 dp[1]은 하나의 수를 필수로 제거한 경우이기 때문에, 최대 연속합을 dp[1]에서만 찾으면 안됩니다. 이에 대한 반례는 수열의 모든 수가 양수인 경우입니다. 따라서, dp[0]과 dp[1]의 모든 수 중 가장 큰 수가 문제의 해입니다.

import sys

input = sys.stdin.readline

n = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))
dp = [list(nums) for _ in range(2)]

for i in range(1, n):
	# 수를 제거하지 않는 경우
    dp[0][i] = max(dp[0][i - 1] + nums[i], nums[i])
    # i번째 수를 제거하는 것을 고려
    dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + nums[i])
    
# dp[0]과 dp[1]의 모든 수 중 가장 큰 수가 문제의 해
print(max(max(dp[0]), max(dp[1])))

🙏 해당 포스팅에 정리된 개념 및 코드에 대한 질문과 피드백은 환영입니다!