[백준/Python] 1912 연속합

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

1912번: 연속합

백준 님의 강의를 참고하였다. 

 

연속된 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제. 

이 문제에서 음수를 제하고 푼다는 생각은 하면 안 된다! 

음수가 있어도 합이 커질 수 있기 때문이다. (ex. 3, -1, 3)

 

그리고 연속된 숫자를 고르고 나면, 

그 앞에 있는 숫자들은 더의상 의미가 없다.(중요!!!)

이전까지의 DP문제들은 이전의 합에 더해가는 방식으로 식을 세웠다면,

이 문제는 이전의 값이 현재의 값과 비교하여 클 경우에만 합하고 그렇지 않다면 앞의 경우를 모두 제외시킨다. 

 

또한 이 문제는 A[i]가 가능한 합의 경우의 수를 다 구해봐야 한다. 

A[i] A[i-1] + A[i] A[i-2] + A[i-1] + A[i] A[i-3] + A[i-2] + A[i-1] + A[i] A[i-4] + A[i-3] + A[i-2] + A[i-1] + A[i] .....

 

이런 식으로 말이다. 

 

위의 식에서 규칙을 찾아보면, 

A[i]인 경우,

A[i]와 A[i-1]...A[i-n]까지의 합을 저장한 dp[i-1]의 합이라고 볼 수 있다. 

따라서 최종식은 A[i]와 A[i]+dp[i-1] 중 최댓값을 저장해 나가는 것이라고 볼 수 있다. (max(A[i], A[i]+dp[i-1]))

 

최종 코드는 다음과 같다. 

n = int(input())

array = list(map(int, input().split()))

dp = [0] * n
dp[0] = array[0]

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

print(max(dp))

 

나름 이제 점화식을 보고 코드를 짤 수는 있게 된 것 같다. 

하지만 규칙을 찾는 것은 아직 너무 어렵다........