백준 1912-연속합 (파이썬)

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

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

예제 출력 1

33

예제 입력 2

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

14

 

예제 입력 3

5
-1 -2 -3 -4 -5

예제 출력 3

-1

 

---

시나리오

주어진 수열의 연속합 중 가장 큰 값을 구해야한다. 물론 완전탐색으로 구할 수도 있다. 이때의 시간 복잡도는 

\(n + (n-1) + (n-2) + (n-3) + \cdots + 1 \)이므로 \( n = 100,000 \)일 때, \(\\ \\S_{100000} = \cfrac{100000*(100000+1)}{2}=5,000,050,000\)으로 제한시간 내에는 당연히 못 푼다.

 

따라서 DP로 문제를 해결해야 한다.

연속합 중 최댓값을 구하는 게 목적이기 때문에, 수열의 특정 항까지의 연속합을 DP테이블에 삽입하는 걸 기본으로 하되, 이전 항까지의 연속합 + 현재 항과 현재 항을 비교했을 때 더 큰 값을 DP테이블에 삽입한다.

전자보다 후자가 더 큰 경우에는 이미 연속 합의 최댓값이 아니기 때문이며, 그 즉시 현재 항부터의 연속합을 DP테이블에 새로 기록한다고 생각하면 되겠다.

 

코드

import math

n = int(input())
#임의의 수열
seq = [0] + list(map(int, input().split()))

dp = [0] * (n + 1)

#dp테이블 첫번째 요소에 수열의 초항을 삽입하여 연속합을 계산할 환경을 만들어준다.
dp[1] = seq[1]

#dp테이블의 이전 요소 + 수열의 현재 요소, 수열의 현재 요소 중 더 큰 값을 dp테이블에 삽입한다.
for i in range(2, n + 1):
    dp[i] = max(dp[i - 1] + seq[i], seq[i])

m = -math.inf
#dp테이블의 요소 중 최대값을 찾음
for i in range(1, n + 1):
    if dp[i] > m:
        m = dp[i]

print(m)

 

피드백

오랜 시간 고민해보다 완전탐색하는 아이디어밖에 떠오르지 않아서 찍듯이 점화식을 만들어봤고 운 좋게 규칙을 찾아 맞출 수 있었다.

DP문제를 여러 개 풀다 보니 이 유형도 풀이가 어느 정도 정형화돼있다는 것을 느꼈다. 경험을 토대로 시간을 단축시키고 더 어려운 문제를 푸는 것을 목표로 하자.