문제 풀이(42)

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

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


class Node implements Comparable<Node>{
    int price;
    int value;

    Node(int price , int value)
    {
        this.price = price;
        this.value = value;
    }

    @Override
    public int compareTo(Node now)
    {
        
        if (this.price == now.price) {
            return now.value - this.value;
        }
       

        return this.price - now.price;
    }


}

public class Main {

    static ArrayList<Node>list = new ArrayList<>();
    static int N, D;
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        D = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int price = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            list.add(new Node(price, value));
        }

        Collections.sort(list);

        int R = 0;
        long sum = 0 , max = Long.MIN_VALUE, diff = 0;

        for (int L = 0; L < N; L++) {
            
            while (R + 1 <= N) {
                diff = list.get(R).price - list.get(L).price;
                if (diff >= D) {
                    break;
                }
                sum += list.get(R).value;
                R++;
            }

            max = Math.max(max, sum);

            sum -= list.get(L).value;

        }

        System.out.println(max);
    }
}

Node 클래스:

Node 클래스는 두 개의 정수 변수 price와 value를 가지고 있습니다. 이 클래스는 Comparable 인터페이스를 구현하며, compareTo 메서드를 재정의합니다. 이 메서드는 Node 객체를 가격을 기준으로 비교하도록 정의되어 있다.

최대 가치 계산:

변수 R은 현재 검토 중인 상품의 인덱스를 나타내며, sum은 선택한 상품들의 가치를 누적하는 변수이다. max는 최대 가치를 저장하는 변수, diff는 현재 검토 중인 상품과 R 위치의 상품의 가격 차이를 나타낸다.
반복문을 통해 L을 고정하고, R을 이동시키며 가격 차이가 D 이하인 상품들을 선택한다. 그리고 sum을 업데이트하고 max에 최대 가치를 저장한다.
L을 이동할 때, 선택한 상품의 가치를 sum에서 빼준다.