소형기관차

1. 개요

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

2. DP 풀이

def solution():
    N = int(input())
    people = list(map(int, input().split()))
    
    # dummy
    people.insert(0, 0)

    capacity = int(input())

    dp = [[0]*(N+1) for _ in range(4)]
    accHumans = [0]

    for i in range(1, N + 1):
        accHumans.append(accHumans[i - 1] + people[i])

    for i in range(1, 4):
        for j in range(capacity, N + 1):
            humans = accHumans[j] - accHumans[j - capacity]
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - capacity]+humans)

    print(dp[3][N])

solution()