[BOJ] 10025번 게으른 백곰

개요

슬라이딩 윈도우를 이용해 푸는 문제

문제링크

코드

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

public class Baekjoon10025 {
    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[1000001];
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int g = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            
            arr[x] = g;
        }
        int window = 0;
        for (int i = 0; i < k+1 && i < arr.length; i++)  
            window += arr[i];
        
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            int low = i - k -1;
            int high = i + k + 1;
            if(low >= 0)
                window -= arr[low];
            if(high < arr.length)
                window += arr[high];

            if(max < window)
                max = window;
        }
        bw.write(max+"\n");
        bw.flush();
    }

해결 과정

이 문제는 단순히 생각해보면 브루트포스로 백곰의 위치를 처음칸부터 한칸씩 옮기면서 다시 계산해보는 방법을 떠올릴 수 있지만 배열의 크기가 10만개나 될 수 있고 좌우로 얻을 수 있는 K의 크기도 매우 크기 때문에 효율성이 많이 떨어진다.

그래서 슬라이딩 윈도우 알고리즘으로 윈도우를 처음에 지정하고 한칸씩 옆으로 이동하는 방식으로 게산해야 한다.

한칸씩 이동할 때마다 이동하기 전의 맨 왼쪽 칸의 값을 빼주고 새로 이동한 칸의 값을 더해주는 방식으로 최대값을 판별해나가면 해결된다.

결과