[다이나믹 프로그래밍] 1912번 - 연속합

[백준] 1912번 - 연속합

(한줄평) 점화식을 세우는데 헷갈리긴 했지면 결국 혼자서 풀어낸 문제! 나중에 한번쯤 복습해보면 좋을 것 같다~

 

풀이 시간: 20분 이내

1) 문제 해결 아이디어

크기가 n인 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합의 최댓값을 구하는 문제다.

처음에 이 문제가 헷갈렸던 이유는 i번째 원소(graph[i])를 포함 시키는 경우, 포함 시키지 않는 경우 2가지로 나눠야한다고 생각했기 때문이다. 그래서 자꾸 이상한 답이 나왔다...

이 문제에서 중요한 점은 연속된 숫자를 선택한다는 것이고 최소 1개이상의 수를 선택해야 한다는 점이다.

 

<i번째 원소를 무조건 선택한다고 했을 때 경우의 수>

1. i번째 원소 선택, (i -1)번째 원소 선택한 경우, (i - 2)번째는 선택할 수도 있고 안할 수도 있다.

그러므로 i번째 원소값 + (i - 1)번째가 마지막 연속된 숫자인 최대합 이 1번 경우의 최대합이다.

2. i번째 원소 선택, (i -1)번째 원소 선택하지 않은 경우, (i - 2)번째 부터는 무조건 선택할 수 없다. (선택하면 연속된 숫자가 아니게 되므로)

그러므로 i번째 원소값이 2번 경우의 최대합이다.

 

<점화식>

2) 소스코드

n = int(input())  # 수열 크기
graph = list(map(int, input().split()))  # 크기가 n인 수열
d = [0] * n  # i번째까지 연속된 수의 합의 최댓값
d[0] = graph[0]

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