아이디어

• 가격이 D 이상 차이나지 않도록 인접해야 한다는 점에서 투 포인터를 떠올려야 한다.
• 선물을 가격순으로 정렬하고 투 포인터(Sliding window) 기법을 사용해야 한다.
• 오른쪽 포인터를 옮기다 가격이 D 이상 차이나게 된다면 왼쪽 포인터를 한 칸 옮겨보는 작업을 반복하며, 합 중 최댓값을 찾는다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;
	
	static int N, D;
	static Gift[] gifts;
	static long ans;

	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		D = Integer.parseInt(tk.nextToken());
		
		gifts = new Gift[N];
		for (int i=0; i<N; i++) {
			tk = new StringTokenizer(rd.readLine());
			int p = Integer.parseInt(tk.nextToken());
			int v = Integer.parseInt(tk.nextToken());
			gifts[i] = new Gift(p, v);
		}
		
		Arrays.sort(gifts);
		
		long sum = 0;
		int p=0;	// inclusive
		int q=0;	// exclusive
		ans = sum;
		
		while (true) {
			while (q < N && gifts[q].p - gifts[p].p < D) {
				sum += gifts[q].v;
				q++;
			}
			ans = Math.max(ans, sum);
			if (q == N) break;
			
			sum -= gifts[p].v;
			p++;
		}
		
		System.out.println(ans);
	}
	
	static class Gift implements Comparable<Gift>{
		int p, v;
		Gift(int p, int v) {
			this.p = p;
			this.v = v;
		}
		@Override
		public int compareTo(Gift o) {
			return Integer.compare(this.p, o.p);
		}		
	}
}

메모리 및 시간

• 메모리: 45020 KB
• 시간: 592 ms

리뷰

• 정렬 기준을 처음에 V로 잡았다가 애 먹었다.
• "인접한 N개"라는 단어가 있으면 투 포인터를 떠올려보자.