2559번: 수열

문제

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 구하는 문제입니다.

• 입력: 첫째 줄에 전체 날짜의 수 N과 합을 구하기 위한 연속적인 날짜의 수 K가 주어집니다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어집니다.
• 출력: 연속적인 K일 동안의 온도의 합이 최대가 되는 값을 출력합니다.

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

풀이

연속된 구간의 합을 매번 반복문으로 구하면 시간 초과가 발생할 수 있습니다. 이를 해결하기 위해 누적 합(Prefix Sum) 배열을 미리 만들어두고 활용하는 O(N) 풀이입니다.

1. 누적 합 배열 생성: 크기가 N + 1인 psum 배열을 선언합니다. 입력을 받음과 동시에 이전 누적 합에 현재 값을 더하여 psum[i] = psum[i - 1] + 현재 온도 형태로 누적 합 배열을 완성합니다.
2. 연속된 K일의 합 계산: 어떤 배열에서 인덱스 a부터 b까지의 합은 누적 합 배열을 이용해 psum[b] - psum[a - 1]로 단번에(O(1)) 구할 수 있습니다. 여기서는 연속된 K일의 합을 구해야 하므로, i번째 날짜를 끝으로 하는 K일의 합은 psum[i] - psum[i - K]가 됩니다.
3. 최댓값 갱신 및 주의점: 온도에는 음수가 포함될 수 있으므로, 최댓값을 저장하는 변수 ans의 초기값은 0이 아닌 Integer.MIN_VALUE로 설정해야 합니다. 반복문을 돌며 가장 큰 합을 찾아 ans를 갱신합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int k = Integer.parseInt(st.nextToken());

       // 1. 누적 합(Prefix Sum) 배열 생성
       int[] psum = new int[n + 1];
       st = new StringTokenizer(br.readLine());
       for (int i = 1; i <= n; i++) {
          psum[i] = psum[i - 1] + Integer.parseInt(st.nextToken());
       }

       // 음수 기온이 존재할 수 있으므로 초깃값을 가장 작은 정수로 설정
       int ans = Integer.MIN_VALUE;
       
       // 2. 누적 합을 이용하여 K일 간의 합을 O(1)에 계산하고 최댓값 갱신
       for (int i = k; i <= n; i++) {
          ans = Math.max(ans, psum[i] - psum[i - k]);
       }

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

누적 합 (Prefix Sum), 슬라이딩 윈도우 (Sliding Window)