JAVA 백준 2559 수열 (누적합)

 

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

---

문제

1. 첫째 줄에 N( 2 <= N <= 100000 )과 K( 1 <= K <= N )을 공백을 두고 입력.
2. 둘째 줄에 온도를 나타내는 수 N개를 배열에 추가. 수( -100 <= 수 <= 100 )
3. 입력된 N개의 온도에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력.

---

 

최종 코드

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

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

        int maxTemperature = -10000000;

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] list = new int[N];
        int[] sum = new int[N - K + 1];
        int count = 1;

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            list[i] = num;

            if (i >= K) {
                sum[count] = (num + sum[count - 1] - list[count - 1]);
                count++;
            } else {
                sum[0] += num;
            }
        }


        for (int i = 0; i < N - K + 1; i++) {
            if (sum[i] > maxTemperature) {
                maxTemperature = sum[i];
            }
        }

        System.out.println(maxTemperature);
    }
}

 

maxTemperature는 모두 -100이 100000일동안 나온다는 가정 하에 -10000000로 설정하였음.

 

i가 K번 더해지기 전까지는 0번에 더하고, K번 더해진 이후에는 이전에 더해졌던 것에 새로운 날짜를 더하고 가장 멀리 있는 한 날짜를 빼는 방식으로 누적합 배열을 채웠다.

메모리 초과가 날까봐 어떻게 해야 되나 싶었는데 다행이 메모리가 넉넉한 것 같다.