[백준/1912] 연속합 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = [0] + list(map(int, input().split()))
dp = [-1001] * (n+1)

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

print(max(dp))

---

✔ 설명

가장 큰 값을 구해야하기 때문에 이전까지의 합에 현재 숫자를 더한 값과 현재 위치의 값 중 더 큰 값을 dp에 저장한다.

---

✔ 후기

1개 이상의 연속된 수를 더해야한다고 하길래 arr에서 1개 합, 2개 합, 3개 합 이렇게 하나씩 다 구하고 값을 비교해야 한다고 생각했다. 분명 그렇게 구현되지 않을 것 같았는데 저 생각이 머리를 지배하고 있었다.

max도 사용한다는걸 어렴풋이 알고 있었지만 막상 어떤 값과 어떤 값을 비교해야 하는지 dp[i]의 i는 선택된 숫자들의 개수가 들어가는건지 꽤나 삽질했다.