문제 출처

단계별로 풀어보기 > 누적 합 > 수열
https://www.acmicpc.net/problem/2559

문제 설명

온도를 측정한 전체 날짜의 수 N, 합을 구하기 위한 연속적인 날짜의 수 K가 주어질 때, 연속적인 K 일동안 온도의 합이 가장 큰 값을 계산하는 프로그램을 구하라.

접근 방법

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

public class 수열 {
    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());

        int arr[] = new int[N];


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

        arr[0] = Integer.parseInt(st.nextToken());
        for(int i = 0; i < N-1; i++){
            arr[i+1] = arr[i] + Integer.parseInt(st.nextToken());
        }

        int max = arr[K - 1];

        for(int i = K; i < N; i++){
            int sum = arr[i] - arr[i-K];
            max = Math.max(sum,max);
        }

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

처음 max = arr[k - 1]은 누적합 처음을 기준한다.

시간 복잡도는 O(N + (N-K)) 이므로 O(N)이다.

문제푼 흔적