[BOJ] 백준 12892 : 생일 선물 (java)

🧪 12892 생일 선물

---

난이도 : 🌟 골드 4
유형 : 투포인터

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

 

📝 문제

---

오늘은 강민이의 생일이다. 강민이는 친구 N명이 있는데, 각 친구는 모두 강민이를 위한 생일 선물을 하나씩 준비했다. 각각의 선물은 P와 V를 가진다. P는 해당 선물의 가격이며, V는 만족도로 해당 선물을 받았을 때 강민이가 기뻐하는 정도를 수치화한 것이다.

강민이는 모든 선물을 다 받고 싶지만, 어떤 친구가 준 선물의 가격이 다른 친구가 준 선물의 가격과 D 이상 차이 나면 더 낮은 가격의 선물을 준 친구가 미안함을 느끼게 될 수 있다. 강민이는 자신의 행복도 중요하지만, 생일선물로 친구에게 미안함을 느끼게 하고 싶지는 않다. 고심 끝에 강민이는 일부 친구들에게만 선물을 받기로 결심했다. 누구도 미안하지 않을 수 있게 선물을 받으면서, 강민이가 느낄 수 있는 만족도의 최대 합은 얼마인지 구해보자.

 

입력

 

첫 줄에 친구의 수 N(1 ≤ N ≤ 100,000)과 미안함을 느끼게 되는 최소가격차 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 선물의 가격 P와 만족도 V(0 ≤ P ≤ 1,000,000,000, 0 ≤ V ≤ 1,000,000,001)가 주어진다.

 

출력

 

 

한 줄에 강민이가 최대 얼만큼 기뻐할 수 있는지를 출력하라.

 

🚧  주의할 점

---

 

🧐 핵심 로직 

---

1. 프로그램은 입력 데이터를 처리하여 각 정보의 위치(p)와 가치(v)를 저장하고, 이를 기반으로 슬라이딩 윈도우 기법을 이용해 최적의 구간을 찾는다.

    1 - 1) 첫 번째 줄에서 n(정보의 개수), d(최대 거리 차이)를 읽어온다.

    1 - 2)  n개의 정보(p, v)를 객체로 리스트 infos에 저장한 후, 위치(p)를 기준으로 오름차순 정렬한다.

 

2. 슬라이딩 윈도우를 이용해 최적의 구간을 찾는다.

    2 - 1)  left와 right 두 포인터를 사용해 윈도우 내 위치 차이가 d 미만인 범위를 유지하며, 해당 구간의 가치(v)의 합을 계산한다.

    2 - 2)  right 포인터를 확장하며 조건에 맞는 범위의 합을 누적하고, 최대값을 계속 갱신한다.

    2 - 3)  조건을 벗어난 경우 left 포인터를 한 칸 이동시키며 범위를 유지하고, 빠지는 값은 합에서 제거한다.

 

3. 계산된 최대 가치의 합을 출력한다.

 

💻 최종 코드 (544 ms)

---

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

public class Main {

    static class Data implements Comparable<Data> {

        int p, v;

        Data(int p, int v) {
            this.p = p;
            this.v = v;
        }

        @Override
        public int compareTo(Data o) {
            return Integer.compare(this.p, o.p);
        }
    }

    static BufferedReader br;
    static int n, d;
    static long res;
    static List<Data> infos;
    public static void main(String[] args) throws Exception {

//      br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        infos = new ArrayList<>();

        fillData();
        slidingWindow();

        System.out.println(res);

        br.close();
    }

    private static void fillData() throws Exception {

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            infos.add(new Data(p, v));
        }

        Collections.sort(infos);
    }

    private static void slidingWindow() {

        int left = 0;
        int right = 0;
        long sum = 0;
        while (true) {

            while (right < n && infos.get(right).p - infos.get(left).p < d) {
                sum += infos.get(right).v;
                right++;
            }

            res = Math.max(res, sum);
            if (right == n) break;

            sum -= infos.get(left).v;
            left++;
        }
    }