[DP] 백준 2208. 보석줍기

문제

링크

보석 사이의 함정, 경보장치를 고려해 최대 가치의 보석을 구해라
함정 : 보석 줍다가 뒤로 못가
경보 : m개 이상을 연속으로 주워야 빠져나올 수 있음
=> 보석 줍기 시작하면 m개 이상 주워야 함

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
dia = [0]+[int(input()) for _ in range(n)]
dp = [0]*(n+1)

for i in range(1,n+1):
    tot += dia[i]
    if 0<i<=m:
        dp[i] = dp[i-1] + dia[i]    
    else:
        dp[i] = tot - min(dp[:i-m+1])

print(max(dp[m:]))