[백준] 1912번 - 연속합 (DP) - 결과 포함

www.acmicpc.net/problem/1912

1912번: 연속합

앞선 문제들과 유사한 문제다보니 비교적 쉽게 해결했다.

연속해서 붙어있는 수열의 합이 가장 큰 것을 구하는 문제이다.

 

일단 연속이라고 했으니 앞에서부터 차례대로 숫자를 살펴본다.

 

만약에 다이나믹 프로그래밍, 메모를 이용하지 않는다면 모든 경우의 수를 계산해서

최댓값을 구할 것이다.

 

효율을 위해 메모를 이용한다.

메모에 적는 내용은 현재 보고 있는 숫자와 이전 결과에 현재 숫자를 더했을 때 둘 중에 더 큰 값이다.

 

예를 들어 다음과 같은 수열이 있다.

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

세 번째 숫자의 입장에서 비교하면

앞에 있는 10과 -4에서 이미 메모한 값과 자기 자신, 즉 3을 더했을 때 값을 비교하는 것이다.

d[1]은 6이므로 3을 더한 9가 3보다 크다. 그러므로 d[2] = 9이다.

 

비교를 하는 이유는 음수가 존재하기 때문이다.

만약 양의 정수만 존재한다면 무조건 수열의 모든 원소를 더한 값이 최댓값일 것이다.

 

내가 지금 차곡차곡 모으고 있는 이 합계에 음의 정수가 들어와서 작게 만들기 전에 이 합은 여기서 끝을  내고

다음부터 새롭게 합계를 차곡차곡 쌓아간다는 개념으로 이해했다.

 

점화식은

d[i] = max(d[i - 1] + data[i], data[i])

이다.

 

이전에는 항상 다른 사람들의 글을 참고해서 해결하다가 스스로 생각해서 해결하고 나니 뿌듯했다.

최근에 계속 다이나믹 프로그래밍 문제를 풀었고 이 문제가 다이나믹 프로그래밍으로 해결하는 것이라는 전제가 깔려있었지만,

그래도 접근하지 못했던 이전의 문제들과 다르게 어떻게 할 지가 보여서 나름 기분이 좋았다.

 

[소스 코드]

n = int(input())

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

d = [0] * n
d[0] = data[0]

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

print(max(d))