백준 1912 (연속합)

백준 1912 (연속합)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/1912

문제 접근

연속합 문제를 들고 왔습니다. 너무 대중적인 문제입니다. n개의 원소를 가진 수열에서, 연속된 몇 개의 수의 합의 최댓값을 구하는 문제입니다. 현재 우리가 모르는, 미지수로 두어야 할 특징은

1) 어디서 시작해서 2) 어디서 끝나는가

즉, 2개의 특징에 의거하여 그 구간의 합을 구하면 되는 문제입니다. 하지만 배열의 크기가 최대 10만으로 꽤 큰 수입니다. 모든 경우에 대해, 다 탐색한다면 O(n^3)의 시간이 걸리게 될 것입니다. 시작 X 끝 X 합 구하는 과정으로 총 O(n^3)의 시간이 걸릴 듯 합니다. 합을 구하는 과정이야, 부분합 아이디어를 사용한다면 상수 시간으로 해결 될 것 같은데, 그래도 O(n^2)의 시간이 걸린다는 것이 문제입니다.

[부분합에 대한 포스팅을 보려면 여기를 클릭하세요.]

생각을 조금 바꿔봅시다. 연속된 수의 합이라는 것이 결국, 내가 i번째 원소를 보고 있을 때, i-1번째 원소까지 연속된 부분합을 안다면? 문제가 조금 쉬워진다는 것입니다.

결국 돌고 돌아 동적계획법 문제라는 것입니다. 연속된이라는 말의 의미는 내가 예전 상태를 알아야 한다는 것이고, 이를 잘 저장해둬서 빠르게 해결하자는 의미입니다.

하지만, i번째까지 봤을 때, 최댓값을 dp[i]에 저장한다면 이는 좋지 않은 생각입니다. 왜냐하면 dp[i+1]을 구하기 위해서, 처음부터 i번째 원소까지의 max값을 구하는 과정에서 또 n의 시간이 필요하므로, 결국 O(n^2)의 시간이 걸립니다. 심지어 이는, 최적의 해도 나오지 않습니다. 이를 해결하기 위해서 dp배열을

dp[i]는 i번째 원소를 무조건 포함하는, 연속된 합의 최댓값

으로 정의를 해보자는 것입니다. 뭔가 좀 생소해보입니다. 어려울 것이 없습니다. i번째 원소까지 최댓값을 저장한다면, 놓치는 구간이 반드시 생길 뿐더러, 과거의 특정 local maximum 상태를 한 번에 뛰어넘지 못한다면, 계속 local에 빠지는 문제가 생기기에, 나는 i번째 원소를 무조건 포함하는 연속된 부분합으로 문제를 쪼개보자는 의미입니다. 즉, 겹치치 않는 최소 단위를 i번째 원소로 설정한다는 의미입니다.

점화식을 생각해보자면,

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

로 생각해볼 수 있습니다. 이의 의미는, 직전까지 최댓값 + 현재 자신 or 현재 자신을 선택한다는 것입니다. 이후 dp 배열을 한 번 쫙 돌면서 최댓값을 뽑아낸다면? 그것이 바로 우리가 구하고자 하는 값이 될 것입니다. 이제 O(n)의 시간으로 문제를 해결할 수 있게 되었습니다!

소스 코드

import sys
n=int(input())
arr=list(map(int, sys.stdin.readline().split()))
dp=[0 for _ in range(n)]
dp[0]=arr[0]

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

마무리하며

연속된 부분합의 최대에 대해서 알아보았습니다. 문제를 겹치지 않게 분할하는 것이 동적 계획법 초석입니다. 궁금하신 내용이 있으시다면 댓글에 달아주세요.