순회강연

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

풀이

문제 안에 함정이 숨겨져 있어서 조금 어려웠다.

강사가 대학에 나가 강연을 하는데 이 때 price와 day를 입력받는다. 여기서 주의해야할 점은 day안에 강연을 하면 된다는 것이다. 즉 1일차에 비용이 더 높지만 day가 1보다 클 경우 강연을 할 수 있다.

풀이는 먼저 강연들을 입력받은 리스트를 day 기준으로 오름차순하고 dayList에 가능한 day들을 입력받았다.

이후 dayList에서 최대부터 시작해서 역순으로 탐색하면서 비용이 가장 높은 강연을 선택하는 식으로 구현했다.

그런데 이보다 더 직관적이고 쉽게 풀이할 수 있었다.

강연 리스트를 비용 기준으로 내림차순으로 정렬하고 해당 날짜에 이미 강연이 잡혀있다는 식으로 큐에서 꺼내면서 탐색을 하면 쉽게 풀 수 있다. (boolean 배열 사용)

코드

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

public class Main {
    static int n, m, k;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);

        if (n == 0)
            bw.write("0\n");
        else {
            ArrayList<Pair> lecList = new ArrayList<>();
            ArrayList<Integer> dayList = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                String[] line = br.readLine().split(" ");
                int p = Integer.parseInt(line[0]);
                int d = Integer.parseInt(line[1]);
                lecList.add(new Pair(p, d));
                if (!dayList.contains(d))
                    dayList.add(d);
            }
            lecList.sort(Pair::compareTo);
            dayList.sort(Comparator.reverseOrder());

            int idx = 0;
            int max = dayList.get(0);
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());

            int c = max;
            int sum = 0;

            for (int i = max; i > 0; i--) {
                while (idx < n && lecList.get(idx).d >= i) {
                    priorityQueue.offer(lecList.get(idx).p);
                    idx++;
                }
                if (c != 0 && !priorityQueue.isEmpty()) {
                    c--;
                    sum = sum + priorityQueue.poll();
                }
            }
            bw.write(sum + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

class Pair implements Comparable<Pair> {
    public int p;
    public int d;

    public Pair(int p, int d) {
        this.p = p;
        this.d = d;
    }

    @Override
    public int compareTo(Pair o) {
        return -1 * Integer.compare(this.d, o.d);
    }
}