백준 12847번
https://www.acmicpc.net/problem/12847

문제

---

생각하기

---

• 누적 합과 슬라이딩 윈도우의 기초를 활용한 문제이다.

동작

누적 합 기법에서는 모든 합을 입력받으면서 말 그대로 누적합을 미리 계산하고,

M까지 의 합을 구할때는 arr[i] - arr[i - M]를 하면 M까지 의 누적 합에서 구간 합을 구할 수 있다.

슬라이딩 윈도우도 비슷한데

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

미리 누적 합을 구하는 것이 아닌, 누적 합을 해가면서 가장 처음에 합해진 값과, 새로운 다음 값의 차이를 더해가면서 가장 큰 M구간 합의 최대값을 구한다.

결과

코드

---

누적 합

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static long[] arr;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

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

        sb.append(max);
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new long[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());
        }

    } // End of input()
} // End of Main class

슬라이딩 윈도우

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static long[] arr;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();
        
        long sum = 0;
        for (int i = 0; i < M; i++) {
            sum += arr[i];
        }

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

        sb.append(ret);
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

    } // End of input()
} // End of Main class