BOJ 2559 - 수열 링크
(2023.08.09 기준 S3)

문제

연속적인 N일 동안 측정한 온도가 N개가 주어진다. 이 때, 연속적인 K일의 온도의 합이 최대가 되는 값 출력

알고리즘

슬라이딩 윈도우

풀이

값의 변경이 없고, 모든 위치에 대한 구간의 합을 구하는 것은 슬라이딩 윈도우가 유리하다.

처음에 [0, K - 1] 구간의 합을 구한 뒤, [1, K], [2, K + 1], ... [N - K, N - 1] 구간을 하나씩 구하면 된다. 이 때, 구간의 끝만 더해주고, 구간의 시작점만 빼주면서 구하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, K; cin >> N >> K;
    int A[N]; for (int i = 0; i < N; i++) cin >> A[i];

    // 윈도우(구간)의 크기는 K
    int answer, result = 0;
    for (int i = 0; i < K; i++) result += A[i]; // [0, K - 1] 구간
    answer = result;

    for (int i = K; i < N; i++){ // [i - K + 1, i] 구간
        result += A[i];
        result -= A[i - K];
        answer = max(answer, result);
    }

    cout << answer;
}

• Python

import sys; input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))

# 윈도우(구간)의 크기는 K
answer = result = sum(A[:K]) # [0, K - 1] 구간
for i in range(K, N): # [i - K + 1, i] 구간
    result += A[i]
    result -= A[i - K]
    answer = max(answer, result)

print(answer)