백준(baekjoon) 1912번: 연속합(실버 2, 파이썬 PYTHON) - 동적 계획법 1

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

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

1912번: 연속합

 

import sys

n=int(sys.stdin.readline())
num_list=list(map(int,sys.stdin.readline().split()))
sum=[]
sum.append(num_list[0])

for x in range(1,n):
  sum.append(max(sum[x-1]+num_list[x],num_list[x]))

print(max(sum))

 

※ 동적 계획법 1

 

 

● 먼저 n을 입력받은 후, 주어지는 숫자들을 num_list 배열에 저장한다. 그 후 sum 이라는 빈 배열을 정의해준다.

 

● sum에 num_list 배열의 첫번째 요소를 append 해준다.

 

● 그 후 변수 x 가 1부터 n-1 까지 돌게 한 후, sum[x-1] + num_list[x] 와 num_list[x] 의 값 중 더 큰 값을 sum 에 append 해준다. (각 단계에서 sum 에 append 되는 값은 num_list[x] 를 포함하는 연속 합 중 만들어 질 수 있는 가장 큰 값이다. sum[x-1] + num_list[x] 값은 지금까지 만들어온 연속 합에 다음 원소를 더해주어 연속 합을 늘려간다는 의미이고 단순히  num_list[x] 를 append 하는 경우에는 연속 합을 새로 시작하겠다는 의미이다.)

 

● 그 후 sum 에 들어있는 값 중 최대값을 출력해주면 답을 구할 수 있다.

 

결과