[백준] 1781번. 컵라면(JAVA)

문제

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

---

풀이(17분)

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

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

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

        @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 deadline = Integer.parseInt(st.nextToken());
            int cup = Integer.parseInt(st.nextToken());
            problems.add(new Problem(deadline, cup));
        }

        Collections.sort(problems); // 데드라인 기준 정렬

        // 최소 힙: 지금까지 선택한 문제들 중 최소 컵라면을 유지
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (Problem p : problems) {
            pq.offer(p.cup);
            // 문제를 풀 수 있는 날 수보다 많아지면, 최소 컵라면 제거
            if (pq.size() > p.deadline) {
                pq.poll();
            }
        }

        int total = 0;
        while (!pq.isEmpty()) {
            total += pq.poll();
        }

        System.out.println(total);
    }
}

---

문제 풀이 전략

 

리스트를 사용해 유지를 하려고 했지만 생각보다 복잡해져 우선순위 큐를 도입하여 해결했다.

커스텀 정렬을 할 줄 안다면 그렇게 어려운 문제는 아니라고 느껴졌다.