[BOJ/JAVA] 1781번: 컵라면

1781번: 컵라면

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

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

키워드

• 문제를 푸는데는 단위 시간 1

• 각 문제의 데드라인은 N이하의 자연수이다.

• 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231 보다 작거나 같은 자연수

---

구현

잘못된 접근 방법

1. 데드라인의 오름차, 컵라면 수의 내림차순으로 정렬한다.

2. 앞에 있는 것 중 데드라인에 문제가 없는 것을 모두 선택한다.

위 방법으로 문제를 해결하게 되면 아래의 반례가 생긴다.

3
1 5
2 10
2 11

이 경우에 정렬은 다음과 같이 이루어진다.

위 알고리즘대로 진행하면 5 + 11 = 16의 값을 반환한다.

하지만 최대로 받을 수 있는 보상은 11 + 10 = 21 이다.

올바른 접근 방법

static int solution()

• problemList는 문제를 푸는데는 항상 1의 단위시간이 소모되므로, 데드라인의 내림차순, 보상의 내림차순으로 정렬한다.

• 가장 늦게 해결할 수 있는 문제는 최대한 늦게 해결하도록 한다.

• availableQueue는 항상 보상의 내림차순으로 정렬한다.

• i :: N→0 까지 그 시각을 끝으로 해결할 수 있는 문제를 추출하여 availableQueue에 삽입한다.
  • 해당 날짜에 해결하면 가장 이득인 문제를 availableQueue에서 하나 추출한다.

• result를 반환한다.

---

코드

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

public class java_1781 {
    static int N;

    static PriorityQueue<Problem> problemList;

    static class Problem implements Comparable<Problem> {
        int deadLine;
        int reward;

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

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

    }

    static int solution() {
        int result = 0;

        PriorityQueue<Problem> availableQueue = new PriorityQueue<>(new Comparator<Problem>() {
            @Override
            public int compare(Problem o1, Problem o2) {
                return o2.reward - o1.reward;
            }
        });

        // N 시각에 해결할 수 있는 문제 추출
        for (int i = N; i > 0; i--) {
            while (!problemList.isEmpty()) {
                Problem problem = problemList.peek();
                if (problem.deadLine >= i) {
                    availableQueue.add(problem);
                    problemList.poll();
                } else {
                    break;
                }
            }

            // reward의 내림차순 이므로...
            if (!availableQueue.isEmpty()) {
                result += availableQueue.poll().reward;
            }
        }

        return result;
    }

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

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

        // 데드라인이 가까운 것 우선
        // 컵라면 수가 많은 것 우선

        // 문제의 경우
        // 현재 시간 1
        // 1 - 5, 2 - 10, 2 - 11
        // 의 경우
        // 1 - 5를 포기하는 것이 맞다.

        // 컵라면 수의 내림차순으로 정렬해보자
        // 7 6 2 1 4 5 1
        // 해당 데드라인 가장 끝에 문제를 해결한다.
        // 아니면 그 전 날에 해결한다.

        problemList = new PriorityQueue<>();

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

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

            problemList.add(new Problem(deadLine, reward));
        }

        int result = solution();
        System.out.println(result);

        br.close();
    }
}

---

Uploaded by N2T