백준 2559 수열 Java: 누적합으로 연속 K일 최대 합 구하기

백준 2559번 ‘수열’은 N일 중 연속된 K일의 온도 합이 가장 큰 값을 구한다. 누적합 prefix[i]를 앞에서부터 i개 값의 합으로 만들면 모든 길이 K 구간을 한 번씩 확인할 수 있다.

• 백준 2559번 수열

구간 합 공식

prefix[0] = 0으로 두고 다음처럼 누적한다.

prefix[i] = value[0] + ... + value[i - 1]

그러면 index start부터 end까지의 합은 prefix[end + 1] - prefix[start]다. 길이가 K인 구간의 오른쪽 끝을 prefix index end라고 표현하면 더 간단하다.

window sum = prefix[end] - prefix[end - K]

end를 K부터 N까지 움직이며 최댓값을 갱신한다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int dayCount = Integer.parseInt(tokenizer.nextToken());
        int windowSize = Integer.parseInt(tokenizer.nextToken());
        int[] prefix = new int[dayCount + 1];

        tokenizer = new StringTokenizer(reader.readLine());
        for (int day = 1; day <= dayCount; day++) {
            prefix[day] = prefix[day - 1]
                    + Integer.parseInt(tokenizer.nextToken());
        }

        int answer = Integer.MIN_VALUE;
        for (int end = windowSize; end <= dayCount; end++) {
            int sum = prefix[end] - prefix[end - windowSize];
            answer = Math.max(answer, sum);
        }

        System.out.println(answer);
    }
}

왜 answer를 0으로 시작하면 안 되는가

모든 온도가 음수일 수 있다. answer = 0으로 시작하면 실제 가능한 모든 구간 합보다 큰 0을 그대로 출력할 수 있다. Integer.MIN_VALUE 또는 첫 번째 window의 합으로 초기화해야 한다.

경계도 함께 확인한다.

• K = 1: 원소 하나씩 비교한 최댓값
• K = N: 전체 합 하나가 답
• 모든 값이 음수: 가장 덜 작은 연속 합을 선택

시간 복잡도는 prefix 생성과 window 순회가 각각 O(N)이므로 전체 O(N), 공간은 O(N)이다. 길이 K만 유지하는 sliding window로도 O(N) 시간에 풀 수 있고 추가 공간을 줄일 수 있다.

두 구현을 비교했던 기록

원문에는 입력을 받으면서 i >= K가 되는 즉시 답을 갱신하는 version과, prefix를 모두 만든 뒤 두 번째 loop에서 답을 구하는 version을 함께 적었다. 두 방식의 asymptotic complexity는 같다. 전자는 loop 하나에 끝내고, 후자는 전처리와 query 단계를 눈으로 분리하기 쉽다.

당시에는 가볍게 풀 수 있었던 문제로 보인다고 남겼다. 다시 정리할 때 더 중요한 지점은 loop 수 하나의 차이보다 index 정의와 negative-only 입력의 초기값이다. 문자별 구간 query는 백준 16139 인간-컴퓨터 상호작용, 2차원 확장은 백준 25682 체스판 다시 칠하기 2에서 볼 수 있다.

검증 범위

Java source를 수동 검토하고 K = 1, K = N, all-negative sequence와 작은 random sequence를 모든 window를 직접 더하는 oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.