[백준] 소형기관차

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

2616번: 소형기관차

DP 문제입니다. 먼저, 각 인덱스를 시작으로 소형기관차가 연속적으로 태울 수 있는 손님의 수를 계산하여 저장한 다음

각 연속적으로 저장되어 있는 칸이 1 ~ 3번째에 해당하는 경우에 태울 수 있는 최대 손님의 수를 계산해주면 됩니다.

import sys

sys.stdin = open("input.txt","r")
input = sys.stdin.readline


n = int(input())
passengers = list(map(int, input().split()))
m = int(input())

cur = sum(passengers[:m])
memo = [cur]

left, right = 0, m
# 각 인덱스를 시작으로 끌 수 있는 손님들의 수
# ex) 1 ~ 3, 2 ~ 4, 3 ~ 5
while right < n:
    cur -= passengers[left]
    cur += passengers[right]
    left += 1
    right += 1
    memo.append(cur)


#dp[i][j]: j번째 인덱스를 시작으로 i번째 소형 기관차에 탈 수 있는 손님의 최대의 수
dp = [
    [0] * len(memo)
    for _ in range(4)
]

for j in range(len(memo)):
    for i in range(1, 4):
        if j < m:
            dp[i][j] = memo[j]
		# 현재 칸을 시작으로 하는 손님들을 태우거나 태우지 않는 경우중 최대를 선택
        dp[i][j] = max(dp[i - 1][j - m] + memo[j], dp[i][j - 1])

print(dp[3][len(memo) - 1])