[백준] 2559번. 수열 (JAVA)

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

---

문제

---

풀이

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int x = 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 < x; i++) sum += arr[i];

        int max = sum;

        for (int i = x; i < n; i++) {
            sum += arr[i] - arr[i-x];
            if (max < sum) {
                max = sum;
            }
        }

        System.out.println(max);

    }
}

 

21921 블로그와 유사한 문제이다. 투포인터 중에서도 슬라이딩 윈도 개념을 도입해서 문제를 해결한다면 어렵지 않게 해결할 수 있다.

 

먼저 초기 간격을 max값으로 잡아두고, 한 칸씩 넘어가면서 이 전의 값은 빼고 새로 추가된 값을 더한다. 이때, 합이 이 전의 최댓값보다 더 높게 된다면 이를 max값으로 다시 설정해 둔다.