[Python] 백준 2616번: 소형기관차

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

2616번: 소형기관차

1. 각 기관차 갯수마다 최대로 태울수있는 객차의 수를 구한다.

2. 점화식은 dp[i][j] = max(dp[i][j-1], dp[i-1][j-k] + sum(lst[j-k+1:j+1])) 이다. 

현재 기관차의 갯수가 만약 2라고 가정할 때 이전까지의 값 dp[2][j-1] 과 dp[1][j-k] + 최대 객차의 수 를 비교한다. 

	35	40	50	10	30	45	60
1		75	90	90	90	90	105
2				75+50+10	135	90+30+45	90+45+60
3						210	135+45+60

 

import sys
input = sys.stdin.readline

n = int(input())
lst = [0] + list(map(int, input().split()))
k = int(input())
dp = [[0 for _ in range(n+1)] for _ in range(4)]
for i in range(1, 4):
    for j in range(k*i, n+1):
        dp[i][j] = max(dp[i][j-1], dp[i-1][j-k] + sum(lst[j-k+1:j+1]))

print(dp[3][n])