[백준-1912] 연속합

문제

링크

풀이

import sys
input = sys.stdin.readline

n = int(input())

arr = list(map(int, input().split()))
dp = [0] * n
dp[0] = arr[0]
for i in range(1, n) :
    dp[i] = max(dp[i-1] + arr[i], arr[i])

print(max(dp))

처음에 작성한 코드는 제출할 때 시간초과가 날 것이라고 생각하면서 제출했는데 정말로 시간초과가 발생했다..........................
DP문제를 많이 풀지 않은 상태라 감이 없었고, 도대체 이 문제를 어떻게 DP로 풀 수 있는가 고민했지만 답이 나오지 않았다. 그래서 질문 검색을 통해서 다른 분들의 질문과 답변을 살펴보았고, 이 글 덕분에 문제를 해결할 수 있었다.

처음에 나도 이중 반복문을 통해서 문제를 풀었고, 그러다보니 시간 초과가 날 수 밖에 없었다.
위 글의 답변을 참고하여 i번 원소를 가장 마지막으로 하는 부분 수열 중 합이 최대인 부분 수열의 합을 이용해서 문제를 풀면 된다.

0번 원소를 가장 마지막으로 하는 부분 수열은 0번 원소 자신 밖에 없기 때문에 최대 합도 원소 자신이다. 그러므로 dp[0]을 0번 원소로 넣고, 그 이후로 이전 원소 합 + 현재 원소와 현재 원소 값을 비교하면서 큰 수를 찾아내면 된다.

DP 문제를 많이 풀면서 감을 찾아야 겠다.