1912번: 연속합 (파이썬, 풀이, 정답 코드)

1912번: 연속합 (acmicpc.net)

1912번: 연속합

풀이 자체는 쉬운데, 발상을 하는 게 내 기준에서 어려웠던 문제. 으레 DP문제들이 다 그런 것 같다. 점화식과 DP 문제임을 밝혀내는 게 가장 어려운 과제다. 내가 가장 취약하다고 느끼는 부분인데, 이번에도 온전히 내 힘으로 풀어내는 것은 실패했다. 

아무튼 문제를 보자. 우리는 어떻게 연속된 수를 선택해야 값이 최대가 되는지 한번에 알 수는 없다. 다만 어떻게 고르더라도 그러한 연속된 수의 양 끝단이 어떤 식으로든 존재할 것을 안다. 문제의 예시로 치자면 양 끝단이 바로 붙어있는 케이스가 될 것이다. 이때 우리는 배열을 순차적으로 탐색하면서, 각 원소를 오른쪽 끝으로 가지면서 연속 합이 가장 최대가 되는 경우를 찾을 수 있다. 

DP

그러니까 이 경우 점화식은 이렇게 될 것이다. 
$P_i$ : 문제에서 주어진 배열의 i번째 원소
$A_i$ : $P_i$를 오른쪽 끝으로 하는 연속된 부분집합 중 가장 큰 총합.
$A_0$은? 왼쪽이 없기 때문에 $P_0$ 자체가 가장 큰 총합이 될 것이다. 이렇게 되면 이제야 비로소 식을 세울 수 있게 된다.

$\Large A_i = max(P_i , P_i + A_{i-1}) $

$A_i$는 $A_{i-1}$이 음수일 경우에는 $A_{i-1}$을 버리고 $P_i$만을 취하도록 만들면 되는 것이다.
이렇게 되면 A라는 배열에는 각 P의 원소를 오른쪽 끝으로 하는 가장 큰 연속합의 값만이 담기게 될 것이다. 이때 우리는 가장 연속합을 원하니 이 중에서 가장 큰 값을 고르면 문제 해결.

정답코드

n = int(input())
inlst = [*map(int, input().split())]
lst = [0 for _ in range(n)]
lst[0] = inlst[0]
for i, j in enumerate(inlst[1:]): lst[i+1] = max(j, lst[i] + j)
print(max(lst))