수입률 - DP

 

import java.io.IOException;
import java.math.BigInteger;
import java.sql.Time;
import java.util.*;

class Lecture implements Comparable<Lecture>{
    int money;
    int day;

    public Lecture(int money, int day) {
        this.money = money;
        this.day = day;
    }

    @Override
    public int compareTo(Lecture o) {
        if(o.day==this.day) return o.money-this.money;
        else return o.day-this.day;
    }
}


public class java {
    static int n,max=Integer.MIN_VALUE;
    public int solution(ArrayList<Lecture> ob){
        Collections.sort(ob);
        int answer =0;
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
        int j=0;
        for (int i = max; i>=1 ; i--) {
            for(;j<n;j++){
                if(ob.get(j).day<i)break;
                pQ.offer(ob.get(j).money);
            }
            if(!pQ.isEmpty())answer+=pQ.poll();
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
    java T = new java();
    Scanner sc=new Scanner(System.in);
     n=sc.nextInt();
    ArrayList<Lecture> arr = new ArrayList<>();
        for (int i = 0; i <n ; i++) {
            int s= sc.nextInt();
            int e=sc.nextInt();
           arr.add(new Lecture(s,e));
           if(e>max)max=e;
        }
        System.out.println(T.solution(arr));
    }
}

 

일단 2중 배열일 경우에  클래스 객체를 만들고 compareable을 구현받아서 조건으로 sort할수 있게 만들어준다.

그 후에는 모두 정렬한후 이번 문제와 같은 경우는 3일차 2일차 1일차에 대해 날짜가 변활할 때 최대 값을 구해주는 문제이므로

primary queue로 사용해 날짜가 바뀔때 최대값을 더해주면 되는 문제이다.