DP(다이나믹 프로그래밍): 백준 1912 파이썬 연속합

문제:

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

1912번: 연속합

 

풀이:

항상 느끼는 거지만 다이나믹 프로그래밍 문제는 코드는 정말 간단하지만 규칙과 점화식을 생각해내는 

과정이 너무 어렵다. 이 문제도 연속합을 어떻게 구하는지 생각해내는 게 어려웠고, 코드는 간단했다.

 

반복문을 돌려 dp 배열에 저장되어있는 앞 값들의 연속합 + 현재 값과 현재 값 중 큰 것을 골라서 dp 배열에

저장해나가면 된다.

 

• 10, -4, 3, 1, 5, 6, -35, 12, 21, -1

다음과 같이 이루어진 배열을 입력 받았을 때, 현재 값이 12일 때를 생각해보자. * 답은 33(12+21)이다.

앞에서부터 저장되어온 가장 큰 연속합은 dp[6]이고, 현재 값은 arr[7]이다.

가장 큰 연속합을 구하기 위해서는 dp[6] + arr[7]과 arr[7] 중 더 큰 값을 골라 저장해주면 되는데,

답을 보면 dp[6] + arr[7]이 아닌 arr[7]이 선택되었음을 알 수 있다. 누적되어온 연속합 + 현재 값이 현재 값

12보다 작기 때문.

 

정답:

import sys
input = sys.stdin.readline

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

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

print(max(dp))