[우선순위큐][Java][BOJ] #31680. 열심히 일하는 중

#우선순위큐  #Silver2

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

 

🌷 문제 설명

✏️ 백준 연습문제: #31680. 열심히 일하는 중
송이는 이번 학기에 할 일이 매우 많다. N$N$개의 일 중 어떤 일부터 해야 할지 고민하던 중 송이에게 좋은 아이디어가 떠올랐다! 바로 해야 할 일 각각의 중요도를 산정하고, 중요도가 높은 일부터 하는 것이다. 송이는 하루에 하나의 일만 처리할 수 있으며, 일을 처리한 후 그 일의 중요도는 M$M$만큼 감소한다. 일의 중요도가 K$K$ 이하가 되면 그 일은 완료한 것으로 간주한다. 중요도를 일별로 산정하던 중 송이는 문득 일하면서 본인이 매일 느낄 만족감이 궁금해졌다. 오늘의 만족감은 전날의 만족감을 Y$Y$, 오늘 할 일의 중요도를 P$P$라 할 때 ⌊Y/2⌋+P$\lfloor Y/2 \rfloor+P$와 같다.
예를 들면 다음과 같다. 전날 송이의 만족도가 21$21$이고, 송이가 오늘 할 일의 중요도가 10$10$, M$M$의 값이 4$4$라고 가정했을 때 송이가 오늘 느낄 만족감은 ⌊212⌋+10$\lfloor \frac{21}{2} \rfloor+10$ = 20$20$이 된다. 이후 송이가 오늘 한 일의 중요도는 4$4$만큼 감소해서 6$6$이 된다.
송이가 해야 할 일의 개수 N$N$, 일을 처리했을 때 감소하는 중요도 M$M$, 완료한 것으로 간주하는 중요도의 최댓값 K$K$가 주어진 후, i$i$번 일이 가지는 중요도 Di$D_i$가 입력으로 N$N$개 주어진다. 송이가 모든 일을 끝낼 때까지 며칠이 걸리는지, 그리고 모든 일을 끝낼 때까지 송이가 일별로 느낀 만족감을 한 줄마다 출력하자. 단, 첫날의 경우 전날의 만족감을 0$0$으로 간주한다.


⌨️ 입력
첫째 줄에 정수 N, M, K가 공백으로 구분되어 주어진다. (2≤N≤2000;1≤M≤5;1≤K≤3)$(2 \leq N \leq 2 \, 000; 1\leq M \leq 5; 1 \leq K \leq 3)$ 
둘째 줄부터 N개의 줄에 걸쳐 해야 하는 일의 중요도 정수 Di$D_i$가 주어진다. (M<Di,K<Di,Di≤1000)$(M< D_i, K < D_i, D_i \leq 1 \, 000)$ 

🖨️ 출력
첫째 줄에 송이가 일을 다 하기 위해 걸리는 날의 수를 출력한다.
둘째 줄부터 일을 끝내는 날까지 일별로 느낀 만족감을 한 줄씩 구분해 출력한다.

입출력 예

입력	출력
2 5 3 10 18	5 18 22 21 18 14

 

💡 해결 포인트

1.  우선순위 큐... 일단 시간초과..

 

🌷 내 코드

1.  우선순위 큐(시간초과)

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

        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]); // 해야 할 일 수
        int M = Integer.parseInt(line[1]); // 하루에 감소하는 중요도
        int K = Integer.parseInt(line[2]); // K 이하가 되면 완료

        // 중요도를 내림차순 정렬하는 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < N; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }

        int days = 0;          // 총 소요일
        int satisfaction = 0;  // 전날(이전)까지의 만족도
        List<Integer> dailyList = new ArrayList<>(); // 일자별 만족도 기록

        // 큐가 빌 때까지 반복 (모든 작업 완료 시 종료)
        while (!pq.isEmpty()) {
            // 1. 오늘 처리할 작업(가장 중요도가 높은 작업)을 꺼낸다.
            int current = pq.poll();

            // 2. 오늘 만족도 = floor(어제 만족도 / 2) + 오늘 처리할 일의 중요도
            int todaySatisfaction = (int) Math.floor(satisfaction / 2.0) + current;
            // 전날 만족도 갱신
            satisfaction = todaySatisfaction;
            dailyList.add(satisfaction);

            // 3. 오늘 처리한 일의 중요도 감소
            current -= M;

            // 4. 남아있는 중요도가 K보다 크면 내일 다시 해야 하므로 우선순위 큐에 넣음
            if (current > K) {
                pq.add(current);
            }

            // 하루 지남
            days++;
        }

        // 결과 출력
        System.out.println(days);
        for (int sat : dailyList) {
            System.out.println(sat);
        }
    }
}

 

 

🌷 코멘트

머냐.. 마지막 문젠데 ㄷ찜찜하게...ㅠ

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com