[백준 2559] 수열

1. 요약

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보는 문제.

2. 아이디어

단순하게 연속적인 며칠에 대한 간격만 맞추는 식으로 구현하면 시간 초과가 난다. 예를 들어 온도를 측정한 전체 날짜 수, N이 10만이고 합을 구하기 위한 연속적인 날짜의 수, K가 9만일 경우,

1+2+3+4+...+9만
2+3+4+5+...+9만1
3+4+5+6+...+9만2
...

다시 말해서 10만 x 9만 = 90억의 연산을 수행하게 된다. 따라서 투 포인터와 함께, 누적합을 이용하여 해결해야한다. 몇 일동안 측정한 온도를 담는 배열 A가 아래와 같다고 하자.
A = [-1, -2, 5, 10, -50, 10]

여기서 누적합을 적용하면 아래와 같다.
table = [-1, -3, 2, 12, -38, -28](i.e. 각 인덱스 x에 대해 처음 인덱스에 해당하는 배열 값부터 인덱스 x에 해당하는 배열 값을 더한 결과)

만약 K=3일 경우, 온도를 측정한 4번째날에 대한 온도의 합은 table[3]-table[0]와 같다. 다시 말해, 누적합을 이용하면 각 날짜에 대한 연속적인 온도의 합을 구하는 과정에서 중복연산을 줄일 수 있다. 이 사실을 이용하여, 문제의 답을 구하면 된다.

3. 코드

import sys

n, k = map(int, sys.stdin.readline().rsplit())
arr = list(map(int, sys.stdin.readline().rsplit()))
table = [0] * (n+1)
answer = -int(1e9)
start, end = 0, 0

while end < n:
    table[end+1] += table[end] + arr[end]
    if end - start + 1 == k:
        seq_total = table[end+1] - table[start]
        answer = max(seq_total, answer)
        start += 1

    end += 1

print(answer)