문제 풀이(63)

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

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

/**
7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.
 */

 class Node implements Comparable<Node>{
    int payment;
    int duration;

    Node(int payment, int duration){
        this.payment = payment;
        this.duration = duration;
    }

    @Override
    public int compareTo(Node n){

        if(this.payment == n.payment){
            return this.duration - n.duration;
        }

        return n.payment - this.payment;
    }

    @Override
    public String toString(){
        return payment+" "+duration;
    }
 }

public class Main {

    public static void main(String[] args) throws IOException {
        
        PriorityQueue<Node> pq = new PriorityQueue<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int max = 0;

        boolean[] used ;

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

            int p = Integer.parseInt(st.nextToken()); 

            int d = Integer.parseInt(st.nextToken());

            pq.offer(new Node(p, d));

            max = Math.max(max, d);
        }

        used = new boolean[max + 1];
    

        int sum = 0;

        while (!pq.isEmpty()) {
        
            Node now = pq.poll();

            for (int i = now.duration; i > 0; i--) {
                

                if (used[i] == false) {
                    

                    used[i] = true;

                    sum += now.payment;

                    break;

                }


            }
        }


        System.out.println(sum);
    }
}

문제풀이방법

이 문제는 강연 스케줄을 통해 최대한의 수익을 얻는 문제를 그리디 알고리즘으로 해결하는 방법에 대해 설명하고 있습니다. 기본적으로, 짧은 기간의 강연에 높은 강연료를 받는 전략을 취하는 것이 바람직하지만, 이 방식만으로는 최대 수익을 보장할 수 없습니다. 예시로, 강연료와 강연 기간이 각각 (10,2), (20,3), (20,3), (20,3)로 주어졌을 때, 단순히 짧은 기간의 강연을 우선적으로 선택하면 10, 20, 20의 수익을 얻게 되지만, 이는 최대 수익이 아닙니다.

따라서, 높은 강연료를 우선적으로 선택하고, 강연료가 동일할 경우에는 강연 기간이 짧은 순으로 선택하는 전략을 채택합니다. 이 방식을 통해, 위의 예시에서는 20, 20, 20의 최대 수익을 얻을 수 있습니다. 이러한 선택 메커니즘을 구현하기 위해 (강연 기간, 강연료) 쌍을 우선순위 큐에 저장하고, 강연료를 기준으로 내림차순 정렬, 강연료가 같을 경우 강연 기간을 기준으로 오름차순 정렬하여 우선순위 큐에서 순차적으로 꺼내며 최대 수익을 계산합니다. 가능한 강연 날짜 내에서 최대 수익을 얻기 위해 해당 날짜까지의 스케줄을 체크하며, 최종적으로 계산된 총 수익을 출력하는 방식으로 문제를 해결합니다.