[BOJ 1912] 연속합(Python)

문제링크

연속합

풀이 전 계획 및 생각

처음에는 음수와 양수가 바뀌는 점을 기준으로 부분합을 구하는 방식과 dp를 이용하는 방법 2가지를 생각했었다.
음수와 양수가 바뀌는 점을 기준으로 부분합을 구하는 방식은 '1 2 3 -4 1000' 과 같은 케이스를 처리가 불가능하다는 것을 확인하고 바로 dp를 이용하기로했다.
문제를 해결하기위해서 아래의 2개의 배열을 사용했다.
arr #index번째 원소까지 고려했을 때, 최대 연속합을 저장하는 배열
arr2 #input을 받는 배열

n 이 1인 경우는 바로 그 수를 출력하면 된다.
그렇지 않은 경우는
i를 1부터 n까지 반복하면서 i번째 원소를 i-1번째까지의 연속합과 더한게 i번째 원소보다 크다면 i번째를 포함해서 계속 연속합을 계산을 진행한다.
i번째 원소가 크다면, i번째 원소부터 새롭게 연속합을 구해나가면된다.

풀이

import sys

n = int(sys.stdin.readline())
arr = [0]*n
arr2 = list(map(int,sys.stdin.readline().split()))
if n == 1:
    print(arr2[0])
else:
    arr[0] = arr2[0]

    for i in range(1,n):
        if arr[i-1] + arr2[i] >= arr2[i]:
            arr[i] = arr[i-1] + arr2[i]
        else:
            arr[i] = arr2[i]
    print(max(arr))

풀이하면서 막혔던 점과 고민했던 점

처음에 양수, 음수로 구분해서 나누는 생각을 버리는게 어려웠었다. 하지만, 극단적인 테스트케이스를 사용해보면서 쉽게 해결할 수 있었다.

풀이 후 알게된 개념과 소감

점화식만 잘 세우면 충분히 쉽게 풀린다는 것을 다시 한 번 알 수 있었다.