[파이썬, Python] 백준 2559: 수열

문제

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

2559번: 수열

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
nums = list(map(int, input().split()))
part_sum = sum(nums[:k])
max_sum = part_sum

for i in range(k, n):
    part_sum += nums[i] - nums[i - k]
    max_sum = max(part_sum, max_sum)

print(max_sum)

설명

처음에는 간단하게 인덱스로 구해서 각 구간의 합을 정하고 최댓값을 출력하려고 했으나 시간초과 발생.

슬라이딩 윈도우라는 알고리즘을 이용해서 해결했다.
이 문제의 경우 더하는 부분이 크게 변하지 않는다.

예를 들어 0번부터 5번까지의 인덱스를 더해서 계산을 했으면,
다음 합을 계산할 때는 1번부터 6번까지를 계산하게 된다.
이때, 1번부터 5번의 값은 그대로 유지하고
0번을 빼주고 6번을 더해준다면 조금 더 빠르게 구할 수 있다.

이를 구현해서 계산한 코드이다.