[PS] BOJ1781 컵라면 ( greedy ) with JAVA

1781번: 컵라면

 

 

◎ 문제풀이

 

문제마다 데드라인이 정해져 있을 때, 컵라면을 최대로 몇 개까지 받을 수 있는지를 구하는 문제이다.  이 문제는 그리디 풀이에 HeapQueue를 떠올리면 간단히 풀리는 문제이다. ( 나는 떠올리지 못했다.. ) 단위시간이 1씩 늘어가면 컵라면을 받을 수 있는 개수도 바뀐다. 시간의 변화에 따른 최적해를 구해야 하므로 그리디로 접근해야 한다. 

 

단위시간 1을 하루로 생각해보자. 한 문제를 푸는데 하루가 걸린다. 데드라인이 2일이라면 이틀 안에 풀면 된다. 

 

 

 

 

최적해를 구하려면 데드라인이 촉박한 문제부터 풀어야 한다. 그럼 문제1 -> 문제2 -> 문제3 순으로 풀면 된다. 

 

그러면 보상이 1  + 1 + 10이 되어서 12가 된다.

 

만약 문제1을 풀지 않고 3일 안에 풀면 되는 문제4를 풀면 어떻게 될까?

 

그러면 보상이 10 + 1 + 10이 되어서 21이 된다. 

 

 

다시 말하여, 데드라인 외에 보상이라는 또 다른 우선순위가 존재한다. 

 

 

그럼 이를 토대로 알고리즘을 만들어 보자.

 

1일 : 문제1을 푼다

2일 : 문제2를 푼다.

3일 : 문제3을 푼다.

4일 : 문제4는 데드라인이 3일이라 풀지 못한다. 

 

3일 동안 문제를 네 개를 풀어야 한다. 그러므로 하나가 빠져야 한다. 문제 네 개 중에 가장 보상이 적은 것을 빼면 된다.  최솟값을 빠르게 구할 수 있는 자료구조에는 HeapQueue가 있다.  JAVA에는 PriorityQueue가 HeapQueue 구조로 이루어져 있다. 

 

정리하면, 가장 기본이 되는 우선순위인 데드라인을 기준으로 문제들을 정렬한 다음에, 문제를 하나씩 가져와 PriorityQueue에 넣는다. 문제 하나당 하루이므로 PriorityQueue에 들어간 문제의 개수는 소요시간을 의미한다. 문제4까지 PriorityQueue에 넣으면 문제 네 개가 들어가 있다. 그러면 문제를 모두 푸는데 4일이 걸린다. 그런데 문제4는 3일 안에 풀어야 하므로,  네 개 문제 중에 하나는 제거되어야 한다. 그러므로 PriorityQueue에서 가장 앞에 있는 문제(보상이 가장 적은 문제)를 POP 하면 된다. 

 

개인적으로, HeapQueue를 활용하여 다수의 우선순위를 제어하는 그리디 풀이를 경험해본 적이 없어서 쉽지 않은 문제였다.  

 

◎ 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//BOJ1781 컵라면 ( HeapQueue )
public class Main {
    public static class Problem implements Comparable<Problem>{
        int deadLine;
        int reward;

        public Problem(int deadLine,int reward){
            this.deadLine = deadLine;
            this.reward = reward;
        }

        @Override
        public int compareTo(Problem o){
            return this.deadLine - o.deadLine;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Problem[] problems = new Problem[n];

        StringTokenizer st;
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());

            int deadLine = Integer.parseInt(st.nextToken());
            int reward = Integer.parseInt(st.nextToken());

            problems[i] = new Problem(deadLine,reward);
        }

        Arrays.sort(problems);
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 디폴트 오름차순 정렬

        for(int i=0;i<n;i++){
            int deadLine = problems[i].deadLine;
            int reward = problems[i].reward;

            pq.add(reward);

            if(pq.size() > deadLine){
                pq.remove();
            }
        }

        int ans = 0;
        while(!pq.isEmpty()){
            ans += pq.remove();
        }

        System.out.println(ans);
    }
}