BOJ10025 게으른 백곰

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

10025번: 게으른 백곰

 

 

누적합 또는 투포인터로 풀이 가능

 

import java.util.*;
import java.io.*;
public class Main
{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input1 = br.readLine().split(" ");
        int n = Integer.parseInt(input1[0]);
        int k = Integer.parseInt(input1[1]);
        
        int[] ice = new int[1_000_001];
        int sum=0;
        for(int i=0 ; i<n; i++){
            String[] temp = br.readLine().split(" ");
            ice[Integer.parseInt(temp[1])] += Integer.parseInt(temp[0]);
            sum += Integer.parseInt(temp[0]);
        }
        
        if(2*k>1_000_000){
            System.out.println(sum);
            return;
        }
        
        int count=0;
        for(int left =1;left<2*k+2;left++){
            count+= ice[left];
        }
        int max = count;
        for(int left =2; left<1_000_000-2*k+1; left++){
            count += ice[left+2*k];
            count -= ice[left-1];
            max = Math.max(max,count);

        }

        System.out.println(max);
	}
}
//   1 2 3 4 5 6 7 8 9 10 11 12 13  14 15
// 5 2 0 0 0 0 4 0 0 0  0  0  0   0  15 0 0 0 0 0 0 0

 

 

아래 방식은 정답 예시인데 클래스를 만들어 배열 1_000_000개를 전부 확인하지 고 bucket의 최대 갯수인 N(<100_000)개로 한다.

import java.util.Arrays;
import java.util.Scanner;

class Main
{
    static class Bucket {
        int g;
        int x;
        Bucket(int g, int x) {
            this.g = g;
            this.x = x;
        }
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();
        Bucket[] buckets = new Bucket[N];
        for (int i = 0; i < N; i++)
            buckets[i] = new Bucket(sc.nextInt(), sc.nextInt());

        Arrays.sort(buckets, (o1, o2) -> o1.x - o2.x);

        int nextIndex = 0;
        int maxSum = 0;
        int currentSum = 0;
        for (int i = 0; i < N; i++) {
            while (nextIndex < N && buckets[nextIndex].x - buckets[i].x <= 2 * K) {
                currentSum += buckets[nextIndex++].g;
            }
            maxSum = Math.max(maxSum, currentSum);
            currentSum -= buckets[i].g;
        }
        System.out.println(maxSum);
    }
}