백준 13904: 과제

문제

풀이

점수가 높은 순으로 우선순위 큐에 넣어준다.
과제를 최대한 마감일에 가까운 날짜에 해준다.

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n=Integer.parseInt(br.readLine());
        PriorityQueue<Task> pq=new PriorityQueue<>();
        int max=0;
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            int d=Integer.parseInt(st.nextToken());
            int s=Integer.parseInt(st.nextToken());
            pq.add(new Task(d,s));
            max=Math.max(max,d);
        }

        int ans=0;
        int[] v=new int[max+1];
        while(!pq.isEmpty()){
            for(int i=pq.peek().deadline;i>0;i--){
                if(v[i]==0){
                    v[i]=1;
                    ans+=pq.peek().score;
                    break;
                }
            }
            pq.poll();

        }
        System.out.println(ans);
    }

    static class Task implements Comparable<Task>{
        int deadline;
        int score;

        public Task(int deadline, int score) {
            this.deadline = deadline;
            this.score = score;
        }


        @Override
        public int compareTo(Task o) {
            if(o.score==this.score)return this.deadline-o.deadline;
            return o.score-this.score;
        }
    }
}

#우선순위큐 #그리디