백준 13904 (과제) - java

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

13904번: 과제

문제 :

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

 

유형 : 그리디 + 정렬 + 우선순위 큐

 

접근

• 우선 가장 점수가 큰 과제부터 해결해야 한다. 해당 과제를 가능한 늦게 하는 것이 포인트 !
• 가장 큰 값인 100 5 라는 값이 있을 경우 해당 과제를 5일(마감 바로 전)에 하는 것이다.

전체 코드

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

public class Main {
    static int n = 0;

    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());

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> {
                    if(x.v == y.v)
                        return y.d - x.d;

                    return y.v - x.v;
                }
        );

        for(int i=1;i<=n;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int d = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            Node node = new Node(d,v);
            pq.add(node);
        }

        boolean[] v = new boolean[1001];
        int result  = 0;
        while(!pq.isEmpty()){
            Node cur = pq.poll();

            int tmpDay = cur.d;

            for(int i = tmpDay;i >=1;i--){
                if(!v[i]){
                    v[i] = true;
                    result += cur.v;
                    break;
                }
            }
        }
        System.out.println(result);
        br.close();
    }
}
class Node{
    int d;
    int v;

    Node(int d,int v){
        this.d = d;
        this.v = v;
    }
}