컵라면

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

문제 해결 요약

우선순위 큐에 넣고 그리디하게 상황에 맞게 뽑으면 되는 문제
그래서 우선 적으로 데드라인을 오른차순으로 같은 데드라인 일 경우 컵라면 개수를 내림차순으로 PrioriyQueue 를 구성하였다.
하지만 문제는

	1 25
    2 100
    3 50

과 같은 경우 데드라인이 우선이기 때문에 1,2를 선택하게 되어 125가 나오지만 최선의 수는 2,3을 선택한 150이다.
이럴 경우 새로운 값이 들어왔을때 뽑은 문제들 중에서 가장 낮은 값을 제거하고 새로운 값을 넣으면 된다(어차피 데드라인 순으로 정렬하였기 때문에 데드라인을 고려안해도된다)

순서도

코드

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

public class Main {
    private static int N;

    public static void main(final String[] args) throws IOException {
        problem(new InputStreamReader(System.in));
    }

    public static void problem(final InputStreamReader isr) throws IOException {
        final BufferedReader br = new BufferedReader(isr);
        N = Integer.parseInt(br.readLine());
        final PriorityQueue<Problem> heap = new PriorityQueue<>((p1,p2) -> p1.compare(p2));
        for (int i = 0; i < N; i++) {
            final String[] input = br.readLine().split(" ");
            heap.add(new Problem(input));
        }
        int time = 1;
        final PriorityQueue<Problem> solved = new PriorityQueue<>((p1,p2) -> p1.cnt - p2.cnt);
        while(!heap.isEmpty()){
            final Problem problem = heap.poll();
            if (time <= problem.deadline){
                solved.add(problem);
                time ++;
            } else {
                if (solved.peek().cnt < problem.cnt){
                    solved.poll();
                    solved.add(problem);
                }
            }
        }
        int answer = 0;
        while(!solved.isEmpty()){
            answer += solved.poll().cnt;
        }
        System.out.println(answer);
    }

    private static class Problem{
        private final int deadline;
        private final int cnt;

        private Problem(final int deadline, final int cnt) {
            this.deadline = deadline;
            this.cnt = cnt;
        }

        private Problem(final String[] input){
            this(Integer.parseInt(input[0]),Integer.parseInt(input[1]));
        }

        private int compare(final Problem problem){
            if (this.deadline == problem.deadline){
                return problem.cnt - this.cnt;
            }
            return this.deadline - problem.deadline;
        }
    }
}