BOJ_2109_순회강연 (Java)

[Gold III] 순회강연 - 2109

문제 링크

성능 요약

메모리: 21660 KB, 시간: 288 ms

분류

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

제출 일자

2025년 3월 31일 21:06:40

문제 설명

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

입력

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

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

문제 풀이

처음에 d일이하인줄 모르고 d일만 가능한줄 알고 너무 쉽게 풀었다가 다시 풀었다. d일 이하의 최대 일수에 배치하도록 TreeSet을 이용했고 floor메서드를 통해 특정값 포함 이하중에서 최대값을 반환했다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 * 20:25 ~ 21:05
 */

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

public class Main {
    class Lecture implements Comparable<Lecture>{
        int day, pay;
        public Lecture(int day, int pay){
            this.day = day;
            this.pay = pay;
        }

        @Override
        public int compareTo(Lecture o) {
            return o.pay - this.pay;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int n;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2109_순회강연/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        Lecture[] lectures = new Lecture[n];
        int maxD = 0;
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            maxD = Math.max(maxD, d);
            lectures[i] = new Lecture(d, p);
        }
        Arrays.sort(lectures);

        TreeSet<Integer> ts = new TreeSet<>();
        for(int i=1; i<=maxD; i++){
            ts.add(i);
        }

        int res = 0;
        for(Lecture l : lectures){
            int ableD = ts.floor(l.day)==null ? 0 : ts.floor(l.day);
            ts.remove(ableD);
            if(ableD != 0) res += l.pay;
        }
        System.out.println(res);
        br.close();
    }
}