[DP] 백준 연속합 1912번 with Python3

 

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

1912번: 연속합

문제

 

내 풀이

n = int(input())

arr = list(map(int, input().rstrip().split()))
# print(arr)
dp = [0] * n

temp_stack = []

for i in range(n):
    temp = arr[i]

    if i == 0:
        if arr[i] >= 0:
            dp[i] = temp
            continue
        elif arr[i] < 0:
            dp[i] = temp
            temp_stack.append(temp)
            continue

    if temp >= 0:
        if temp_stack:
            if abs(sum(temp_stack)) < dp[i-1]:
                dp[i] = dp[i-1] + temp - abs(sum(temp_stack))
                temp_stack = []
            else:
                dp[i] = temp
                temp_stack = []
        else:
            dp[i] = dp[i-1] + temp

    elif temp < 0:
        temp_stack.append(temp)
        if dp[i-1] < 0 and temp > dp[i-1]:
            dp[i] = temp
        else:
            dp[i] = dp[i-1]

    # print(f'지금은:{i}')
    # print(dp)

print(max(dp))

해설

dp[i]에 저장되는 값을 해당 수열까지에서의 최대 합으로 구상을 했었다. 하지만 진행 도중 어려움을 느끼고 dp[i]에는 i가 포함되는 최대합의 값이 담기는 쪽으로 방향을 틀었다. 

 

그리고 정답 풀이를 본 결과 이 방향을 처음부터 고수했다면 훨씬 간결하고 효율적인 코드가 나왔을 것이다.

 

 

정답 풀이

import sys

n = int(sys.stdin.readline())

arr = list(map(int, sys.stdin.readline().split()))

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

print(max(dp))

출처:chaeyong Lee

 

해석

위에서 설명했듯이 , dp[i]에는 i를 포함한 최대값 (0~i 범위) 이 저장된다. 결과적으로 max(dp)를 통해 최대 합을 쉽게 찾아 낼 수 있다.