BOJ(백준) 1912번 연속합 파이썬

1912번: 연속합

---

코드

import sys
r = sys.stdin.readline
N = int(r())
num = list(map(int,r().split()))
dp = [0] * N
dp[0] = num[0]
for i in range(1, len(num)):
    dp[i] = max(0, dp[i-1] + num[i])

ans = max(dp)
if ans==0:
    print(max(num))
else:
    print(ans)

 

해설

처음에는 2차원 배열 dp를 이용해 모든 경우의 수(매 시점마다)의 부분합을 구했으나 메모리 초과가 뜨는 바람에 해결하지 못했다. 어떻게 하면 필요한 값들만 효율적으로 저장할까에 대해 고민하다 위의 코드와 같이 하나씩 더해나가면서 그 시점의 부분합이 마이너스가 되는것을 방지하기 위해 max 를 이용해 그럴 경우 0을 저장하도록하였다. 마지막으로 기존 num 의 모든 값이 마이너스인 경우 최종 결과를 0으로 반환하는 문제점을 하기 위해 이 경우 num 리스트에서 최대값을 출력하도록 코드를 작성하였다.

 

결과