연속합

1912_연속합의 응용 문제다.

먼저 1912번부터 살펴보자.

dp를 활용해서 풀 것이다. dp에 처음 숫자부터, 해당 숫자까지 연속된 수의 최대합을 저장한다.

dp[i]에 연속된 수의 최대합을 저장하는 과정을 다시 잘게 쪼개보면,

• dpi-1 + num[i]
• num[i]

둘중 한가지가 dpi임을 알 수 있다.

예시를 들어서 부연 설명을 해보자. 10 -4 3 이렇게 세 숫자가 있다.

• dp[0] = 10 (수는 한 개 이상 선택해야 함으로)
• dp[1] = max(10-4,10) = 6

이제 dp[2]를 구해보자.

• 3 하나를 선택할 수 있다.
• -4 를 선택하면, 10도 같이 선택하는게 연속합을 더 크게 만든다.

이런식으로 왼쪽의 수들을 더하기로 결정하는 과정에서 이 수들을 더했을 때, 나에게 +가 되는지 -가 되는지 판단하는 것이다. 이것을 위의 식으로 표현하면, max(dp[i-1] + num[i], num[i])가 된다.

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

CODE - 연속합

import sys
read = sys.stdin.readline

n = int(input())
num = list(map(int, read().split()))

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

print(max(dp))

연속합2

위의 문제에서 한개의 수를 뺄 수 있는 찬스가 주어지는 문제이다. dp점화식을 조금만 수정해주면 쉽게 풀 수 있다.

우선, 한개의 수를 제거했는지 제거하지 않았는지 판단해야 하기 때문에, dp[i]=[,] 이렇게 dp각각의 원소에 두가지 값을 저장하기로 했다.

dp[i][0]에는 i까지의 숫자 중 제거한 숫자가 없을 때의 최대 연속합을 저장한다. 연속합에서 구한 방식과 정확히 일치한다.

dp[i][1]에는 아래의 세가지 경우 중 가장 큰 값을 저장한다.

• dp[i][0] (숫자를 제거하지 않고 연속합을 구하는 경우)
• dp[i-1][0] (i번째 숫자를 제거하는 경우)
• dp[i-1][1]+num[i] (이미 i번째 이전의 숫자가 제거되어 i번째 숫자는 반드시 더해야 하는 경우)

점화식:

dp[i][0] = max(num[i], dp[i-1][0]+num[i])
dp[i][1] = max(dp[i][0], dp[i-1][0], dp[i-1][1]+num[i])

CODE - 연속합 2

import sys
read = sys.stdin.readline

n = int(read())

num = list(map(int, read().split()))

dp = list([0, 0] for _ in range(n))
dp[0] = [num[0], num[0]]
answer = num[0]
for i in range(1, n):
    dp[i][0] = max(num[i], dp[i-1][0]+num[i])
    dp[i][1] = max(dp[i][0], dp[i-1][0], dp[i-1][1]+num[i])
    answer = max(answer, dp[i][1])
print(answer)

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]