[백준] 1912 - 연속합(DP) - (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/1912

1912번: 연속합

풀이과정 :

동적프로그래밍은 몇번을 풀어봐도 점화식 찾아내는것이 쉽지않다.

DP의 다른 유형 문제와 다른 부분이 있어 연속합이라는것이 계속 이어지지 않고,

특정시험에서 값을 비교하여 그 이전까지는 손절(?) 치는 방식이라,

dp[i] = sum(dp[i-1] + lst[i], lst[i]) 즉 이득이 되는곳 까지 끌고가다가  dp[i-1]이

음수가 되는순간 lst[i]로 갈아타는 방식의 점화식이다.

 

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

답(이미지)

 

후기 : dp는 봐도봐도 새롭고 다양한 점화식이 존재하는것 같다.