[백준]13904: 과제 - JAVA

[백준]13904: 과제

13904번: 과제

풀이

🪑 골드 문제 이길래 처음에 괜히 어렵게 생각해서 DP인가.. 했는데 그냥 구현문제였다.

 

📝 문제를 정리해 보자!

• 하루에 하나의 과제를 할 수 있다.
• 과제를 마무리 할 때마다 마무리한 과제의 점수를 얻는다.

 

 

🔧 문제를 풀어보자!

1. 입력받은 과제들의 정보를 날짜 순서대로 내림차순 한다.
2. 제일 마지막 날짜에서 부터 가능한 과제를 하나씩 우선순위 큐에 넣어준다.
3. 우선순위 큐에서 가장 큰 점수를 갖는 과제를 하나씩 꺼내어 결과에 더해준다.

 

 

🙋‍♀️ 일단 예제를 함께 따라가 보자. 어떤 로직으로 풀지 생각해 보는 과정이다.

- 과제는 순서대로 첫 번째 과제부터 1번 과제라고 부를 것이다.

 

- 각 날짜 별로 해결할 수 있는 과제는 다음과 같다. 

6일) 7

5일) 7

4일) 1 2 6 7

3일) 1 2 5 6 7

2일) 1 2 4 5 6 7

1일) 1 2 3 4 5 6 7

 

이때 풀 수 있는 과제 순서대로 가장 큰 점수를 갖는 과제를 선택한다면 7, 1, 2, 4, 5 순서대로 선택할 수 있으며 우리가 원하는 정답이 된다. 이제 식으로 풀어내 보자!

 

🔹 입력받은 과제들의 정보를 날짜 순서대로 내림차순 한다.

- 내림차순 하여 마지막 날짜부터 현재 풀 수 있는 과제인지 확인해 줄 것이다.

- 이때 마지막 날짜는 입력받는 날짜 중에서 가장 큰 날이 된다.

 

🔹 제일 마지막 날짜에서 부터 가능한 과제를 하나씩 우선순위 큐에 넣어준다.

- 우선순위 큐는 점수 순서대로 내림차순 되도록 설정되어 있다.

- 현재 날짜랑 비교하여 날짜 순서대로 내림차순 되어있는 과제 리스트의 값과 비교한 후 현재 날짜보다 크거나 같아야 풀 수 있는 과제이므로 큐에 담아준다.

 

🔹 우선순위 큐에서 가장 큰 점수를 갖는 과제를 하나씩 꺼내어 결과에 더해준다.

- 현재 풀 수 있는 과제 중에서 가장 큰 점수를 갖는 과제의 정보는 우선순위큐의 맨 앞에 있다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(bf.readLine());
        Node[] works = new Node[n];
        int last_day = -1;
        for(int i = 0; i < n; i++) {
            String str = bf.readLine();
            StringTokenizer st = new StringTokenizer(str);
            int d = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            works[i] = new Node(d, c);
            last_day = Math.max(last_day, d);
        }
        //입력 끝
        Arrays.sort(works, (o1, o2) -> o2.day - o1.day); //날짜 순 내림차순
 
        int result = 0;
        int works_idx = 0;
        PriorityQueue<Node> q = new PriorityQueue<>();
        for(int i = last_day; i > 0; i--) {
            while(works_idx < n && works[works_idx].day >= i) {
                q.offer(works[works_idx++]);
            }
            if(!q.isEmpty()) result += q.poll().score;
        }
        System.out.println(result);
    }
 
    public static class Node implements Comparable<Node> {
        int day;
        int score;
 
        public Node(int day, int score) {
            this.day = day;
            this.score = score;
        }
 
        @Override
        public int compareTo(Node n) {
            return n.score - this.score;
        }
    }
}