[백준] 1781번 - 컵라면 [Java]

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

 

[백준] 1781번 - 컵라면 [Java]

[백준] 1781번 - 컵라면 [Java]

---

1.  아이디어

 

그리디 알고리즘으로 해결할 수 있다.

현재 날짜를 N일부터 1일까지 이동하며 해당 일에 풀 수 있는 문제 중 가장 컵라면을 많이 받는 문제들을 푸는 과정을 반복하면 된다.

---

2. 문제풀이

 

데드라인에 대해 내림차순으로 정렬하는 우선순위 큐와 컵라면 수에 대해 내림차순으로 정렬하는 우선순위 큐를 사용했다.

입력을 받아 데드라인에 대해 내림차순으로 정렬하는 우선순위 큐에 담은 후 for문으로 각 날짜에 대해 해당 날짜에 풀었을 때 컵라면을 받을 수 있는 문제들을 데드라인에 대해 내림차순으로 정렬하는 우선순위 큐에서 컵라면 수에 대해 내림차순으로 정렬하는 우선순위 큐로 옮겼다.

---

3. 코드

 

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

public class Main {

    private static class Problem {
        int deadLine;
        int reward;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        // 데드라인에 대한 내림차순 정렬
        PriorityQueue<Problem> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2.deadLine, o1.deadLine));
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int deadLine = Integer.parseInt(st.nextToken());
            int reward = Integer.parseInt(st.nextToken());
            pq.add(new Problem(deadLine, reward));
        }

        // 컵라면 수에 대한 내림차순 정렬
        PriorityQueue<Problem> pq2 = new PriorityQueue<>((o1, o2) -> Integer.compare(o2.reward, o1.reward));
        int sum = 0;
        for (int day = N; day > 0; day--) {
            while (!pq.isEmpty() && pq.peek().deadLine >= day) {
                pq2.add(pq.remove());
            }

            if (pq2.isEmpty()) continue;

            sum += pq2.remove().reward;
        }

        System.out.println(sum);
    }
}

---

4. 후기