[백준/JAVA] 2559: 수열

[백준/JAVA] 2559: 수열

연속적인 k일의 온도의 합이 최대가 되는 값을 누적합으로 찾아야 한다.

브루트 포스로 풀면 중복 계산이 아주 많이 일어날 수밖에 없는 문제이다. k일의 연속된 합을 구할 때 가운데 값은 중복되고, 달라지는 것은 가장 맨 앞과 가장 맨 뒤의 값이다. 그렇다면 배열에서 구간이 이동할 때 맨 앞과 맨 뒤 값만 변경해 주면 된다.

이렇게 윈도우가 이동할 때 가운데 값을 유지하면서 연산을 최소화하는 것을 슬라이딩 윈도우 알고리즘이라고 한다.

소스코드

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int arr[] = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<n; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int sum = 0;
        for (int i=0; i<k; i++)
        	sum += arr[i];
        /* 연속적인 K일의 온도의 합이 최대가 되는 값을 누적합으로 찾는다.
         * 슬라이딩 윈도우 기법 : 윈도우가 이동할 때 
         * 가장 맨 앞 값을 제외하고 가장 맨 뒤 값을 추가하여
         * 연산을 최소화한다.
         */
        int result = sum;
        for (int i=k; i<n; i++) {
        	sum = sum - arr[i-k] + arr[i];
        	result = Math.max(sum, result);
        }
        System.out.println(result);
    }
}