[백준]2109: 순회강연(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값이 주어진다.

출력

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

예제 입력 1 

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

예제 출력 1 

185

---

풀이

자료구조는 우선순위큐를 사용하였습니다.

가격순으로 내림차순 정렬을 하였고, 만약 가격이 같다면 날짜순으로 내림차순 정렬을 하였습니다.

우리는 N일 이내에만 수행하면 되므로

3
1 5
2 50
2 50

인 경우 50 + 50 = 100이 최대가 되게 됩니다.

정렬은

2 50
2 50
1 5

순으로 되는데 2일짜리는 1일에 수행해도 상관 없으므로 이것을 boolean형 배열을 통해

for(int i = now.d; i>=1; i--) {
    if(day[i]) continue;
    day[i] = true;
    price+=now.p;
    break;
}

현재 날짜부터 1까지중에 자리가 비어있는곳에 수행해준다는 느낌으로 처리해주었습니다.

현재 날짜부터 1로 내려가야 가장 늦은 날에 수행할 수 있음을 유의해야할 것 같습니다.

 

전체 코드

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

public class BJ_2109_G3_순회강연 {
    static class Pay implements Comparable<Pay>{
        int p;
        int d;
        Pay(int p, int d) {
            this.p = p;
            this.d =d ;
        }

        @Override
        public int compareTo(Pay o) {
            if(this.p == o.p) {
                return o.d-this.d;
            }
            return o.p - this.p;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Pay> pq = new PriorityQueue<>();

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

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

            pq.add(new Pay(p, d));
        }

        int price = 0;
        boolean[] day = new boolean[10001];
        while(!pq.isEmpty()) {
            Pay now = pq.poll();
            for(int i = now.d; i>=1; i--) {
                if(day[i]) continue;
                day[i] = true;
                price+=now.p;
                break;
            }
        }
        System.out.printf("%d", price);
    }
}