이번에 풀어본 문제는
백준 2109번 순회강연 입니다.

📕 문제 링크

❗️코드

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

class Req
{
    int p,d;

    public Req(int p, int d) {
        this.p = p;
        this.d = d;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        PriorityQueue<Req> pq = new PriorityQueue<>((o1, o2) -> {
            if(o1.p == o2.p) return o1.d - o2.d;
            return o2.p - o1.p;
        });
        for(int i = 0; i < N; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int tmp_p = Integer.parseInt(st.nextToken());
            int tmp_d = Integer.parseInt(st.nextToken());

            pq.add(new Req(tmp_p,tmp_d));
        }

        int answer = 0;
        boolean [] scheduled = new boolean[10001];
        while(!pq.isEmpty())
        {
            Req cur = pq.poll();
            for(int i = cur.d; i > 0; --i)
            {
                if(!scheduled[i])
                {
                    scheduled[i] = true;
                    answer += cur.p;
                    break;
                }
            }
        }
        System.out.print(answer);
    }
}

📝 풀이

순회 강연을 도는 학자가, d일안에 p의 비용을 받고 강연을 해달라는 총 N개의 (p,d)를 제안 받습니다. 해당 입력 내에서 가장 큰 비용을 발생시킬 수 있는 경우를 구해 출력하는 문제입니다.
먼저 제가 원하는 기준으로 정렬하기 위해 우선순위 큐를 활용해 보았습니다.
당연히 비용이 가장 중요하다고 생각하여 비용을 기준으로 내림차순 정렬한 후, 날짜를 기준으로는 오름차순 정렬해 주었습니다. 이제 스케줄을 짜는 것이 문제였는데, 처음에는 d에 따라 겹치지 않게 가장 큰 비용을 선택하는 방식을 사용했는데, 틀렸다고 나왔습니다. 그 이유는
3
10 2
10 2
1 1
이런 입력에서 발생했습니다. 해당 입력의 답이 당연히 11이라고 생각했지만, 반례들을 찾다보니 1,2번 입력을 선택한 20이 정답이라는 것을 알게 되었고, 저는 문제를 보고 파악하지 못했지만, 10 2 라는 입력 자체가 2일 안에 강연을 하면 되니까 1일차에 해당 입력값을 선택해도 된다는 의미였던 것 같습니다. 따라서 10 2 라는 입력도 1일차에 강연을 할 수 있다는 조건을 고려하기 위해 큐를 탐색하는 while문 안에 방문배열과 역순으로 탐색하는 반복문 하나를 추가해 주어 해결했습니다. 스케줄을 짜는 과정 자체를 역순으로 생각하는 것입니다.
위의 입력을 예를들어보면, 첫 번째 탐색에서 2일차에 10의 비용을 주고 강연하는 것을 선택했다면, 다음 탐색에서의 10 2는 2일차에 스케줄이 있으므로 방문배열에서 걸러지고, i값이 감소함에 따라 1일차의 스케줄을 확인합니다. 1일차는 비어있으므로 두번 째10 2 입력은 1일차에 10일의 비용을 받고 강연을 하는 것으로 채택됩니다.
위 과정을 반복하면, d값에 관계 없이 최대 비용을 구할 수 있습니다.

📜 후기

어쩐지 너무 쉽게 풀리더라니 문제의 예외 케이스를 빠르게 파악하지 못했던 것 같네요.. 문제를 확실히 이해하는 것이 제일 어려운 것 같습니다..ㅠ
이 문제는 곡반정동 때밀이 님이 추천해주셨네요 ㅋㅋㅋ