[파이썬] 백준 1912 연속합

< 기존 풀이 >

for 문을 반복해서 모든 경우의 수를 구했고 당연히 시간 초과가 발생했다. dp 라는 다이나믹 프로그래밍을 활용하는 것은 알고는 있지만 생소해서 적용이 힘들었다.

 

< 해결 방법 > 

dp 라는 리스트를 만들었고 그 리스트에 '현재 까지 연속 합' 이나 '현재 리스트의 값' 중 큰 값을 넣어 준 후 마지막에 리스트의 최댓값을 출력하는 방식을 이용했다. 처음에 볼 때는 무슨 말인지 몰랐지만 코드를 짜보닌 어느정도는 이해를 했다. 

 

import sys
 
a = int(input())
 
 
 
b=list(map(int,sys.stdin.readline().rstrip().split(" ")))
 
 
dp = [0] * (a)
dp[0] = b[0]
 
 
for i in range(1,len(b)):
    dp[i]=max(dp[i-1]+b[i],b[i])
 
print(max(dp))