백준 2208: 보석 줍기 (Python)

접근

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

2208번: 보석 줍기

현재인덱를 포함하는 누적합과, 현재 인덱스가 M번째가 되는 누적합 중 큰 값을 저장하여 문제를 해결할 수 있다.

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
arr = [0]
prefixSum = [0]
for _ in range(N):
    arr.append(int(input()))
    prefixSum.append(prefixSum[-1] + arr[-1])
dp = [0] * (N + 1)
dp[M] = prefixSum[M]

for i in range(M + 1, N + 1):
    dp[i] = max(dp[i - 1] + arr[i], prefixSum[i] - prefixSum[i - M])

print(max(dp))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!