[BOJ] 12892. 생일 선물 (🎁, 투 포인터)

🔗

풀이

선물 가격들은 D이상이 차이나면 안 된다. 최대 값과 최소값의 가격 차이가 가장 클 것이기 때문에 이 값이 D이상이 되면 둘 중 하나를 빼야 한다.

이때 N이 10만이기 때문에 가능한 모든 경우의 수를 조합해서 구하는 것은 2초 내에 연산이 불가능하다. 대신 선물의 가격을 기준으로 어떤 것을 넣을 것이고 뺄 것인지 정할 수 있으므로 선물 가격을 기준으로 하여 오름차순으로 정렬한 후 차례대로 하나씩 선물을 주면서 만족도의 합을 구한다. 그러다가 현재 넣으려고 하는 선물의 가격이 현재 강민이에게 주려고 하는 선물들 가운데 최소인 가격과 D이상 차이날 경우 최소 가격의 선물에 해당하는 만족도를 제거한다.

해당 과정은 투 포인터 알고리즘을 사용하여 풀이했다.

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

public class Main {
    static final int MOD = 1_000_000_007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());
        
        int P;
        int V;
        int[][] gifts = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            P = Integer.parseInt(st.nextToken());
            V = Integer.parseInt(st.nextToken());
            gifts[i][0] = P;
            gifts[i][1] = V;
        }

        Arrays.sort(gifts, (o1, o2) -> o1[0] - o2[0]);
        
        int low = 0;
        long maxSum = 0;
        long tmpSum = 0;
        for (int i = 0; i < N; i++) {
            tmpSum += gifts[i][1];
            while (gifts[i][0] >= gifts[low][0] + D) {
                tmpSum -= gifts[low][1];
                low++;
            }
            maxSum = Math.max(maxSum, tmpSum);
        }

        System.out.println(maxSum);
    }
}