[백준 골드2] 1781번: 컵라면 (우선순위 큐, 그리디) - Java

"스파르타코딩클럽 작심큰일 챌린지" 3일차 챌린저 문제

---

1781번: 컵라면

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

 

문제
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.
문제 번호 1 2 3 4 5 6 7
데드라인 1 1 3 3 2 2 6
컵라면 수 6 7 2 1 4 5 1
위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.
문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.
문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작은 자연수이다.

입력
첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력
첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

예제 입력 1 
7
1 6
1 7
3 2
3 1
2 4
2 5
6 1
예제 출력 1 
15

---

알고리즘: 자료 구조, 그리디 알고리즘, 우선순위 큐

풀이

같은 시간이라면 높은 보상을 선택해야 하므로 우선 순위 구조가 필요해 우선 순위 큐를 사용했다. 매 순간 최적의 선택을 해야 하기 때문에 그리디 알고리즘이다.

 

시도

데드라인과 보상으로 지급되는 컵라면 수가 쌍을 이루는 점 때문에 PriorityQueue에 쌍을 저장하고 정렬을 통해 풀으려고 했는데, 그렇게 해버렸더니 아래의 테스트 케이스를 통과하지 못했다.

 

2

1 25

2 50

2 100

오답: 125 / 정답: 150

 

GPT에게 물어보니 유니온파인드를 하면 문제가 풀리게 할 수는 있다는 것을 알게 되었지만... 이렇게 그래프화해서 푸는 걸 의도한 문제는 아닌 것 같았다.

아래는 유니온 파인드 풀이:

 

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

public class Main {
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }

    static void union(int x, int y) {
        parent[find(x)] = find(y);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) return Integer.compare(b[1], a[1]);
            else return Integer.compare(a[0], b[0]);
        });
        int maxTime = 0;
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            int d = Integer.parseInt(s[0]);
            int r = Integer.parseInt(s[1]);
            pq.offer(new int[]{d, r});
            if (d > maxTime) maxTime = d;
        }
        
        parent = new int[maxTime+2];
        for (int i=0; i<=maxTime+1; i++)
            parent[i] = i;

        int sum = 0;
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int available = find(curr[0]);
            if (available == 0) // 0인 경우 불가능
                continue;
            sum += curr[1];
            union(available, available-1);
        }
        System.out.println(sum);
    }
}

 

아래는 작심큰일 챌린지의 모범답안을 참고해 우선순위 큐와 그리디만으로 푼 풀이이다.

Problem 클래스에서 Comparable 인터페이스를 구현하고 compareTo 메소드를 오버라이딩해 deadline 오름차순 정렬*을 설정했다.

(*-를 사용해서 음수이면 오름차순; 문제 범위 상 오버플로우 x. Integer.compare(this.deadline, o.deadline)와 같다.)

List에 Problem 객체를 담고 정렬한 후 하나씩 꺼내면서 우선순위 큐에 넣는데, 우선순위 큐의 크기 > 객체 p.deadline이면 pq.poll 해서 가장 적은 컵라면 수(의 문제를 푸는 경우)를 버린다.

+) Java에서 PriorityQueue는 min-heap(최소 힙)으로 동작한다. (큐에서 가장 작은 값이 항상 맨 앞에 위치)

+) max-heap을 쓸 경우 PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());와 같이 선언한다.

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

public class Main {
    static class Problem implements Comparable<Problem> {
        int deadline;
        int ramen;

        Problem(int deadline, int ramen) {
            this.deadline = deadline;
            this.ramen = ramen;
        }

        @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());
        List<Problem> problems = new ArrayList<>();
        for (int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            problems.add(new Problem(d, r));
        }
        Collections.sort(problems);
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (Problem p : problems) {
            pq.offer(p.ramen);
            if (pq.size() > p.deadline) {
                pq.poll();
            }
        }
        long count = 0;
        for (int r : pq)
            count += r;
        System.out.println(count);
    }
}