[백준] 1912번 연속합 (Python)

https://www.acmicpc.net/problem/1912

1912번: 연속합

---

풀이과정

①문제 들여다보기

누가봐도 dp문제다. 보텀업 방식으로 이 문제는 해결될 것이다.

 

②아이디어 열기

이 문제를 풀기 위해서는 max함수를 활용하고 역시 하던대로 반복문을 활용해야한다.

dp[i] = max(dp[i],dp[i-1]+dp[i])가 필요함을 느꼈다.

그래서 일단 코드를 짜봤는디

생각보다 짧게 나왔다.

2주전에 한 코드보다 더 좋았다. 그런데 한번 실수를 했었는데,

dp[i] = max(dp[i],dp[i-1]+dp[i],0)이라는 멍청한 코드를 썼기 때문이다.

저렇게 코드를 작성할 경우, 음수만 들어가는 경우에서 '0'만 도출하면서 굉장히 틀린 답을 부른다. 그럼에도 내가 이 코드를 떠올린 이유는, 아마 있는 것만 못한 경우때문에 그런거같은데 굉장히 편협적인 사고였다. 무튼! 그러하다.

 

③최종 코드

n = int(input())
dp = list(map(int,input().split()))
for i in range(1,n):
    dp[i] = max(dp[i],dp[i-1]+dp[i])
print(max(dp))