[자바] 백준 10025 - 게으른 백곰 (boj java)

문제 : boj10025

 

  x는 0부터 1000000까지의 좌표값이다. 그리고 [x-k, x+k] 구간내에 있는 얼음의 합을 구할 수 있다면, 모든 구간을 보면서 최대치만 찾으면 된다.

 

  슬라이딩 윈도우 혹은 prefix sum을 계산해서 구하면 된다. prefix sum으로 할 경우, 좌표별로 prefix sum 배열(이하 ps[])을 만들고 이후 좌표 a에서 잡을 수 있는 얼음의 합은 ps[a+k]-ps[a-k-1]가 될 것이다. 따라서 a를 k부터 n-k까지 증가시키면서 각 O(1)로 a 위치에서의 얼음의 합을 구할 수 있으므로 O(|x|) (x의 크기는 1000000)으로 답을 구할 수 있다.

 

  이하 코드는 슬라이딩 윈도우 방식으로 짠 코드이다. 슬라이딩 윈도우도 비슷하다. a를 k부터 n-k까지 증가시키면서, 2k+1 크기의 윈도우를 옆으로 밀듯이 한칸씩 민다. 그럼 윈도우에서 제외된 가장 좌측값 하나를 제거하고, 이번에 추가된 가장 우측값을 더해주면 [a-k, a+k] 구간 얼음의 합을 구할 수 있다.

 

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int g = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            arr[x]+=g;
        }
        int sum = 0;
        for (int i = 0; i < 1+2*k && i <= 1000000; i++) {
            sum += arr[i];
        }
        int max = sum;
        for (int i = 1+2*k, j = 0; i <= 1000000; i++, j++) {
            sum -= arr[j];
            sum += arr[i];
            if (sum > max)
                max = sum;
        }
        System.out.println(max);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}