백준 1912 풀이 (연속합, 다이나믹 프로그래밍)

이거 진짜 쉬운줄 알았는데 DP로 풀어야해서 헤맸던 문제이다.

처음에는 값을 누적시켜서 DP느낌으로 풀었는데 시간 복잡도가 n제곱이라 자꾸 시간초과가 났다.

그래서 내가 푼 방식이 잘못되었다는 것을 깨닫고 한참을 헤매었다.

n = int(input())
nl = list(map(int, input().split()))
dp = [0 for i in range(n)]
big = -1000
for size in range(n):
    for i in range(n-size):
        dp[i] += nl[i+size]
    tmp = max(dp)
    if tmp > big:
        big = tmp
    print(dp)
print(big)

 

그래서 고친게 다음과 같다.

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

이렇게 풀기위해서는 sum을 잘 정의해야한다.

sum의 역할은 인덱스에 해당하는 값을 포함할때 최댓값을 구해야하는 것이다. 따라서 이전의 최댓값+현재값 vs 현재값을 비교하여 값이 줄어드는지 늘어나는지를 판단하여 큰 값(현재값을 포함할때 큰값)을 새롭게 sum에 갱신해주면된다.

이러한 방식으로 풀게되면 시간복잡도가 n으로 줄어들고 아주 빠르게 연산이 가능해진다.