[Java] 백준 1781 - 컵라면

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

1781번: 컵라면

여러 가지 반례를 생각해보아야 하는 문제

 

이 반례를 보고 도움이 많이 됐다 → https://www.acmicpc.net/board/view/97635

 

예를 들어)

• deadLine 1 cup 2
• deadLine 2 cup 4 / deadLine 2 cup 5 인 경우

 

데드라인 1에서 1개, 데드라인 2에서 1개를 선택하면 cup이 2+5 = 7이지만,

데드라인 2에서 2개를 선택하면 cup이 4+5 = 9이다.

 

 

[방법]

1. PQ 두 개 사용

• PQ 1. 입력값 : deadLine이 짧은 순 → cup라면이 많은 순
• PQ 2. 결과값 : cup라면이 적은 순 

2. PQ 1에서 꺼내서 PQ 2에 넣기

• PQ 1에서 하나씩 꺼내와 PQ 2에 넣음

3. 작업의 개수(=소요 시간)가 PQ 1에서 꺼낸 작업의 마감기한보다 크거나 같은 경우

• PQ 2의 맨 앞의 작업의 cup 개수가 PQ 1에서 꺼내온 작업의 cup 개수보다 작으면 PQ 2의 맨 앞 작업을 꺼낸 후 PQ 1에서 꺼낸 작업을 PQ 2에 넣어줌
• 위와 반대일 경우 그냥 continue

 

 

[구현]

package BOJ_1000;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class boj1781 {
   static class Problem implements Comparable<Problem> {
      int limit;
      int cup;
      public Problem (int limit, int cup) {
         this.limit = limit;
         this.cup = cup;
      }
      @Override
      public int compareTo(Problem o) {
         if(this.limit == o.limit)
            return o.cup - this.cup;
         return this.limit - o.limit;
      }
   }
   private static int N;
   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
      N = Integer.parseInt(br.readLine());
      
      PriorityQueue<Problem> pq = new PriorityQueue<>();
      PriorityQueue<Problem> res = new PriorityQueue<>(new Comparator<Problem>() {
		@Override
		public int compare(Problem o1, Problem o2) {
			return o1.cup - o2.cup;
		}
      });
      
      
      for(int i=0; i<N; i++) {
         String[] str = br.readLine().split(" ");
         int l = Integer.parseInt(str[0]);
         int c = Integer.parseInt(str[1]);
         
         pq.add(new Problem(l,c));
      }
      
      int time = 0, ans = 0;
      while(!pq.isEmpty()) {
         Problem p = pq.poll();
         if(time >= p.limit) {
        	 if(res.peek().cup < p.cup) {
        		 ans -= res.poll().cup;
        		 ans += p.cup;
        		 res.add(p);
        	 }
        	 continue;
         }
         
         res.add(p);
         ans += p.cup;
         time++;
      }
      
      System.out.println(ans);
   }
   
}