[1912/백준/파이썬] 연속합 - DP

---

소스코드

A = int(input())

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

for i in range (1,A):

  numlist[i] = max(numlist[i],numlist[i]+ numlist[i-1])

print(max(numlist))

---

알고리즘

numlist= [10 ,-4 ,3 ,1 ,5, 6 ,-35 ,12, 21, -1] 일 때

[10, 6, 3, 1, 5, 6, -35, 12, 21, -1]
[10, 6, 9, 1, 5, 6, -35, 12, 21, -1]
[10, 6, 9, 10, 5, 6, -35, 12, 21, -1]
[10, 6, 9, 10, 15, 6, -35, 12, 21, -1]
[10, 6, 9, 10, 15, 21, -35, 12, 21, -1]
[10, 6, 9, 10, 15, 21, -14, 12, 21, -1]
[10, 6, 9, 10, 15, 21, -14, 12, 21, -1]
[10, 6, 9, 10, 15, 21, -14, 12, 33, -1]
[10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

 

접근방법

문제를 접했을 때 n 이 100,000이라고 했을 때 드는 생각은 n제곱의 연산 이상하면 안되겠구나였다. (메모리 초과)

그렇다면 dp로 for문 한번을 사용해야한다는 것이라는 생각이 들어 dp로 접근하였다.

 

해설

문제 핵심은 i 번째의 index에 해당하는 숫자에 대한 생각인 것 같다.

numlist가 만약 [10,-4] 이렇게 있었다고 가정을 하면

numlist[0] = 10, numlist [1] = 6일것이다.

이는 너무 자명해서 놓치기 쉬운 부분이 있는데 dp[1]을 결정하는 부분에 대해 생각을 해보면

numlist [0] + numlist [1] 과 numlist [1]을 비교해서 결정한 것이다.

목적지를 numlist[1]이라고 생각하고 출발점이 처음부터 시작이라고 생각해보면 된다.

 

이 생각이 맞는지 numlist[3]에 대해 생각을 해봅시다.

numlist[0] = 10 (0번째까지는 10밖에 없으니 당연한 사실)

numlist[1] = 6 (위에서 설명했듯 numlist[0] + numlist[1] 과 numlist[1] 를 비교한다.)

numlist[2] = 9 ( numlist[1] 까지야 어찌됐든 최댓값이 6이니깐 이거랑 3 더하기 vs 3을 비교한다.)

numlist[3] = 10 계산해보면 된다.

 

dp에 대해 개념이 잡히면 오히려 쉬운 문제이다.