[알고리즘] 동적 계획법(Dynamic Programming) - 백준 1912번 연속합

import sys
input = sys.stdin.readline

n = int(input().rstrip())
numArr = list(map(int, input().rstrip().split(' ')))

for i in range(1, len(numArr)):
    numArr[i] = max(numArr[i], numArr[i-1]+numArr[i])

print(max(numArr))

풀이과정

연속합은 동적 계획법의 가장 기본적인 문제이다.
배열로 받은 값들을 앞에서부터 비교하면서 i번째 값과 그 전까지의 합을 비교해 더 큰 값을 넣는다.

잘못된 풀이

import sys
input = sys.stdin.readline

n = int(input().rstrip())
numArr = list(map(int, input().rstrip().split(' ')))

dp = []

for i in range(n):
    sub = [numArr[i]]
    for j in range(i+1, n):
        sub.append(sub[-1] + numArr[j])
    sub.sort()
    dp.append(sub[-1])

print(max(dp))   

동적 계획법 방법을 생각하지 못했을 때, 더한 모든 값을 비교했다.
당연히 시간 초과가 난다!

동적 계획법을 좀더 잘 적용하는 방법을 배워야할 것 같다 :)