[백준, 파이썬] 1912번 연속합

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

1912번: 연속합

dp문제는 일단 배열에 적어가다보면 해결방법이 보이는것 같습니다. 

 

우선 위 검은색 글자가 주어진 수열이며, 빨간색이 갱신되는 dp 배열에 들어갈 요소입니다. 

최고값만 찾으면 되므로 일단은 다 더해본 후 그중 최고의 값을 찾으면 됩니다. 

 

다만 한가지 규칙이 있는데요 바로 dp[i]와 그 다음 i+1번째의 숫자요소를 더해 본 후 

그값이 i+1번째 숫자요소보다 작을경우는 dp[i+1]번째 값을 i+1번째 숫자요소로 갱신합니다. 

 

왜냐하면 dp[i]와 num[i+1]이 그냥 기존의 num[i+1]값보다 작게된다면, 

num[i+1]부터 숫자를 더해가는것이 기존의 값을 이어가는 것 보다 더 크기 떄문입니다. 

따라서 이와같은 규칙을 염두하여 코드를 작성하면 다음과 같이 간단히 짤 수 있습니다. 

 

n = int(input()) num_list = list(map(int,input().split(' '))) dp = [num_list[0]] for i in range(n-1): best.append(max(dp[i]+num_list[i+1], num_list[i+1])) print(max(dp))