백준 1912번 연속합 파이썬

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

1912번: 연속합

 

내 답안

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

---

 

사실 처음에 코드 짤 때는

N = int(input())
x = list(map(int, input().split()))
dp = [0] * N
for i in range(1):
    for j in range(i, N):
        dp[j] = sum(x[i:j + 1])
 
for i in range(1, N):
    for j in range(i, N):
        dp[j] = max(dp[j], sum(x[i:j + 1]))
 
print(max(dp))

dp 테이블을 처음 만들고 이중 for 문으로 다 계산을 하였다.

하지만 시간 복잡도가 O(N^2)이라 시간 초과가 떴었다.

.

.

그래서 따로 태블릿에 적어 곰곰이 생각을 해보았다.

이중 for 문으로 돌지 않고 그냥 for 문 한 개로도 끝낼 수 있지 않을까?

x[i] = max(x[i], x[i] + x[i - 1])

생각해 보니

이 한 줄 자체가 x[i] 자리를 끝내는 거이기 때문에

for 문 한 줄로도 쉽게 가능한 문제였다.

따라서 이중 for 문을

for 문 한 개로 줄여서 문제를 해결하였다.

for i in range(1, N):
    x[i] = max(x[i], x[i] + x[i - 1])