[백준] 10025번. 게으른 백곰(JAVA)

문제

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

---

풀이(5분)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        // 최대 범위 설정
        int[] arr = new int[1_000_001];

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

        // 슬라이딩 윈도우 초기값
        int total = 0;
        for(int i = 0; i < Math.min(2*K + 1, 1_000_001); i++){
            total += arr[i];
        }
        int max = total;
        for(int i = 2*K+1; i < 1_000_001; i++){
            total -= arr[i - (2*K + 1)];
            total += arr[i];
            max = Math.max(total, max);
        }
        System.out.println(max);
    }
}

---

문제 풀이 전략

 

좌우로 정해진 K만큼의 범위를 탐색해야 하는 것이기 때문에 슬라이딩 윈도우를 적용했다.

처음의 구간을 시작으로 다음 범위의 하나씩 더하고 빼며 탐색을 진행한 것이다.

특히, K가 200만까지 가능하기 때문에 인덱스를 정확히 설정하지 않으면 에러가 터지기 쉽다.

for(int i = 0; i < Math.min(2*K + 1, 1_000_001); i++){

와 같이 범위를 정확히 설정하자.

 

문제의 약간 오역이 있지만 N+1개의 줄까지 정보가 주어지는 것이 맞다.