[백준 - 2109][GOLD 3][해설 X] - 순회강연 (JAVA)

문제 링크

---

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

2109번: 순회강연

 

문제

---

한 저명한 학자에게 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값이 주어진다.

 

출력

---

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

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

        int N = Integer.parseInt(br.readLine());
        //날짜가 길고 금액이 높은 순서로 정렬한 강의 목록
        PriorityQueue<Lecture> pq = new PriorityQueue<>((x,y) -> (x.day == y.day ? y.price - x.price : y.day - x.day));

        int lastDay = 0;

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int price = Integer.parseInt(st.nextToken());
            int day = Integer.parseInt(st.nextToken());

            lastDay = Math.max(lastDay,day);

            pq.add(new Lecture(day,price));
        }

        int day = lastDay;
        int sum = 0;
		
        //현재 날짜에서 가능한 강의 목록
        PriorityQueue<Lecture> readyQ = new PriorityQueue<>((x,y) -> (y.price - x.price));

        while(day > 0){
            //현재 날짜에 가능한 강의 탐색
            while(!pq.isEmpty()){
                if(pq.peek().day != day){
                    break;
                }

                readyQ.add(pq.poll());
            }

            //가능한 강의 중 가장 금액이 큰 강의 선택
            if(!readyQ.isEmpty()){
                Lecture lecture = readyQ.poll();
                sum += lecture.price;
            }
			
            //이전 날짜 선택
            day --;
        }

        System.out.println(sum);
    }
}

class Lecture{
    int day;
    int price;

    public Lecture(int day, int price){
        this.day = day;
        this.price =price;
    }
}

 

 

실행 결과

---

 

 

팁

---

• 선택에 영향을 받지 않는 조건이 무엇인지 생각하자. 이 문제에선 뒤의 날짜의 선택으로 앞의 날짜의 선택에 영향을 끼치지 않으므로 날짜가 선택에 영향을 받지 않는 조건이다.