https://www.acmicpc.net/problem/2616
2616호: 소형 기관차
기관차가 끄는 차량의 수는 첫 번째 줄에 입력됩니다. 숫자는 50,000 미만입니다. 기관차가 끄는 객차의 승객 수는 객차 번호 1부터 시작하여 두 번째 줄에 연속적으로 입력됩니다. 객차 타기
www.acmicpc.net
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))