[백준 - 29814번] 원교수님 과제가 너무 많아요 - Java

문제 링크

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

문제

티어: 골드 1
알고리즘: 그리디, 우선순위 큐

중간고사를 준비 중인 김한양은 원교수님께서 내주신 수많은 과제 때문에 절망했다. 터덜터덜 집에 가던 김한양은 마침 집앞에서 과제를 자동으로 해결해주는 로봇 '과제봇'을 판매하는 과제봇 상인을 만났다. 과제봇을 알게 된 김한양은 직접 과제를 해결하지 않고 과제봇을 구매하여 이용하기로 마음 먹었다.

과제봇 상인은 매일 김한양의 집 앞에서 과제봇을 판매한다. 하지만 과제봇은 너무 비싸서 가난한 대학생인 김한양은 하루에 최대 하나의 과제봇만 구매할 수 있다. 과제봇은 구매한 당일 바로 작동시켜야 하며, 각각의 과제봇은 사용자가 지정한 하나의 과제만을 수행할 수 있다. 과제봇이 과제를 완전히 해결한 시점에 해당 과제에 할당된 포인트가 지급된다.

과제마다 정해진 마감일과 해결하는 데 걸리는 시간, 그리고 과제를 해결했을 때 얻는 포인트가 모두 달라서 모든 과제를 수행하지 못할 수도 있다. 다행히 자비로우신 원교수님께서는 얻은 포인트의 총합이 공지된 커트라인 이상이면 재수강을 면할 수 있도록 해주셨다. 따라서 김한양은 재수강을 면할 수 있을 정도로만 과제를 해결하려 한다. 수많은 과제들을 보고 무기력해진 김한양을 위해 커트라인을 넘기는 데에 과제봇이 최소 몇 개가 필요한지 구해주자.

입력

첫째 줄에 과제의 개수 $N\ (1 \leq N \leq 200\,000)$과 원교수님께서 공지하신 커트라인 $C\ (N \leq C \leq N \times 40)$가 주어진다.

다음 줄부터 $N+1$번째 줄까지 각 과제의 마감일 $d\ (1 \leq d \leq N)$와 과제 해결에 걸리는 기간 $t\ (1 \leq t \leq d)$, 그리고 과제를 해결했을 때 얻는 포인트 $p\ (1 \leq p \leq 100)$가 공백으로 구분되어 주어진다.

예를 들어 $t=3$이라면 과제봇이 해당 과제를 해결하는 데에 $3$일이 소요된다.

또한, $d=3$, $t=2$인 과제를 완료하기 위해서는 적어도 $2$일차에는 과제봇을 작동시켜야 한다. ($2$일, $3$일 이틀간 작동 후 $3$일차에 과제 완료)

출력

커트라인을 넘길 수 있는 방법이 존재한다면 김한양이 사용할 수 있는 과제봇의 최소 개수를 출력한다.

만약 얻을 수 있는 포인트의 최댓값보다 커트라인이 더 높다면 I'm sorry professor Won!을 출력한다.

풀이

커트라인을 넘길 수 있는 방법이 존재한다면 사용할 수 있는 과제봇의 최소 개수를 출력한다.
만약 얻을 수 있는 포인트의 최댓값보다 커트라인이 더 높다면 I'm sorry professor Won!을 출력한다.

먼저, 포인트를 최대한 얻을 수 있는 방법부터 찾아본다. 그래야 커트라인을 넘길 수 있는지 알 수 있기 때문이다.

포인트를 최대한 얻을 수 있는 방법은 일마다 포인트를 최대로 높일 수 있는 과제를 선택하는 것이다.

먼저, 데드라인을 딱 맞춰서 푼다고 했을 때 과제를 시작해야 되는 날짜에 맞게 정렬해 본다.

7 150
1 1 10
7 4 20
3 2 50
6 1 40
7 5 30
5 2 50
4 1 5

1일 차 {10}
2일 차 {50}
3일 차 {30}
4일 차 {20, 50, 5}
5일 차 {40}

1일 차부터 시작하는데, 현재 일 수에 맞게 과제를 유지하는 것 중요하다.
당연히 포인트를 최대로 얻기 위함이기 때문에 포인트가 높은 과제를 유지해야 한다.
이를 위해서 pq를 활용한다.

1 ~ 3일 차까지 진행하면 pq에는 {10, 30, 50}이 있게 된다.

4일 차에서는 3개의 과제가 존재하는데, 이 3개의 과제가 pq에 어떤 요소보다 크다면, 밀어낼 수 있다.

왜냐하면 4일 차에 시작해야 될 과제는 하나만 선택할 수 있는데, 이때 나머지 과제를 더 빨리 시작한다면, 가치가 높은 과제가 버려지는 것을 막을 수 있다.

일단 4일 차에 모든 과제를 넣으면 pq에는 {5, 10, 20, 30, 50, 50} 이렇게 존재하게 되고, 4일 차이기 때문에 4개의 과제만 유지해야 한다.

그래서 가치가 더 낮은 5, 10을 빼주면, pq에는 {20, 30, 50, 50}이 남게 된다.

이를 해석하면,
1일 차에는 50p 과제를
2일 차에는 30p 과제를
3일 차에는 20p 과제를
4일 차에는 50p 과제를
풀었음을 의미한다.

그리고 각 가치가 낮은 것을 우선적으로 빼줬기 때문에 일마다 포인트를 최대로 할 수 있는 과제를 선택할 수 있게 된 것이다.

마지막 5일 차에는 40p 하나이기 때문에 pq에 넣어주면 최종적으로
{20, 30, 40, 50, 50}이 된다.

이 값을 전부 더했을 때 얻을 수 있는 포인트의 최댓값이며, 이 값보다 커트라인이 더 높다면, 절대 커트라인을 넘길 수 없다. 그렇기 때문에 I'm sorry professor Won! 출력해 준다.

만약 커트라인보다 더 높다면, 최종 목적은 과제봇의 최소 개수를 출력하는 것이기 때문에
포인트가 작은 과제들을 하나씩 빼주면 된다.

이 의미는 해당 과제를 푸는 일에 과제봇을 사지 않는다는 의미다.

당연히 포인트를 최대한으로 유지하면서 과제봇을 빼주는 것이 과제봇의 개수를 최소화할 수 최선의 방법이기 때문에 포인트가 작은 과제를 우선적으로 빼주는 것이다.

그래서 20을 뺐을 때 {30, 40, 50, 50}이고, 30을 빼면 커트라인을 넘길 수 없기 때문에 최종 답은 4가 되는 것이다.

이 풀이의 시간 복잡도는 O(NlogN)이다.

소스 코드

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

public class Main {
    static int N, C;
  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());
      C = Integer.parseInt(st.nextToken());
      ArrayList<Integer>[] sc = new ArrayList[N + 1];
      
      for(int i=1; i<=N; i++) {
          sc[i] = new ArrayList<>();
      }
      
      for(int i=0; i<N; i++) {
          StringTokenizer st2 = new StringTokenizer(br.readLine());
          int d = Integer.parseInt(st2.nextToken());
          int t = Integer.parseInt(st2.nextToken());
          int p = Integer.parseInt(st2.nextToken());
          sc[d - t + 1].add(p);
      }
      
      PriorityQueue<Integer> pq = new PriorityQueue<>();
      
      for(int i=1; i<=N; i++) {
          
          for(int j=0; j<sc[i].size(); j++) {
              pq.add(sc[i].get(j));
          }
          
          if(pq.size() > i) {
              //pq의 size가 현재 일보다 크다면. i에 맞춰줘야 됨.
              int sz = pq.size();
              for(int j=1; j<=sz - i; j++) {
                  pq.poll(); //버린다.
              }
          }
      }
      
      ArrayList<Integer> list = new ArrayList<>();
      int sum = 0;
      while(!pq.isEmpty()) {
          int p = pq.poll();
          sum += p;
          list.add(p);
      }
      
      if(sum < C) {
          //포인트를 최대한 모았는데도 커트라인이 더 높다면 불가능.
          System.out.println("I'm sorry professor Won!");
      } else {
          //가능하다면 이번엔 과제봇을 최소화
          int answer = list.size();
          for(int i=0; i<list.size(); i++) {
              if(sum - list.get(i) < C) {
                  //작은 것부터 제외하는데, 커트라인을 못 넘기면 break;
                  break;
              }
              //커트라인을 그래도 넘기면
              answer -= 1;
              sum -= list.get(i);
          }
          System.out.println(answer);
      }
  }
}