[JAVA] 백준 1781번 【G2.컵라면】

문제

1781번: 컵라면

 

---

풀이

1️⃣ 우선 순위 큐와 그리디를 이용한 풀이

 

💡 떠오른 Idea

컵라면을 데드라인이 짧고 컵라면을 많이 주는 문제부터 결정해서 큐에 집어넣는다.

즉, 큐의 크기 = 풀기로 결정한 문제 수 = 내가 문제를 푸는데 사용한 시간이 된다.

그리고, 이후에 나오는 문제들이 내 큐의 크기보다 크거나 같으면서 내 큐에 들어있는 컵라면보다 많이 준다면

내 큐에 들어있던 가장 컵라면을 적게 주는 문제를 제거하고, 추가해준다.

예제로 원리를 설명해보면,

먼저, 데드라인이 짧은 것, 컵라면 수가 많은 것 순으로 정렬을 한다.

1. 첫번째 원소는 데드라인 1 / 컵라면 7이다.

현재 큐는 비어있는 상태로, 이 문제를 풀 수 있다. 따라서 추가 해준다.

현재 큐 = [ 7 ]

2. 두번째 원소는 데드라인 1 / 컵라면 6 이다.

현재 큐는 원소가 1개로 이미 1시간을 사용한 상태이다.

따라서 해당 문제를 바로 큐에 추가해줄 순 없다.

그리고 컵라면 수도 현재 큐에 있는 컵라면 보다 적게 주는 문제이므로 패스한다.

현재 큐 = [ 7 ]

3. 세번째 원소는 데드라인 2 / 컵라면 5이다.

현재 큐의 크기는 1개이므로 해당 문제를 풀 수 있다. 따라서 추가해준다.

현재 큐 = [7, 5]

4. 네번째 원소는 데드라인 2 / 컵라면 4이다.

이번 경우 역시, 이미 2시간을 사용했다.

또한, 큐에 있는 컵라면 수가 모두 4보다 크므로 패스한다.

만약, 큐에 4보다 작은 원소가 있었다면 가장 작은 원소를 빼고 4를 추가해주면된다.

...

이런식으로 진행하면 정답을 반환할 수 있다.

 

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

        int N = Integer.parseInt(br.readLine());

		// 데드라인이 짦은 순, 컵라면이 많은 순
        PriorityQueue<int[]> problems = new PriorityQueue<>((a,b)->{
            int result = a[0]-b[0];
            return result == 0 ? b[1] - a[1] : result;
        });

		// 문제 정보 입력
        while (N-- > 0) {
            String[] input = br.readLine().split(" ");
            int deadLine = Integer.parseInt(input[0]);
            int numOfRamen = Integer.parseInt(input[1]);

            problems.offer(new int[]{deadLine, numOfRamen});
        }

        PriorityQueue<Integer> select = new PriorityQueue<>();

		// 문제 결정
        while (!problems.isEmpty()) {
            int[] problem = problems.poll();
            int deadLine = problem[0];
            int numOfRamen = problem[1];

            if (select.size() < deadLine) {
                select.offer(numOfRamen);
            } else {
                if (select.peek() < numOfRamen) {
                    select.poll();
                    select.offer(numOfRamen);
                }
            }
        }

		// 컵라면 개수 합하기
        long result = 0L;
        for (Integer numOfRamen : select) {
            result += numOfRamen;
        }
        System.out.println(result);

    }
}

 

결과

이 문제와 같이, 우선순위 큐는 특정 조건으로 정렬이 필요할 때, 유용한 자료구조이므로 그리디 문제와 혼합해서 나올 수 있을 것 같다.

 

그리디 문제를 풀 때, 우선 순위 큐를 활용할 수 있는지 생각해보고 접근해야겠다.