[JAVA] 2109 - 순회강연 💛3 : 최대를 만들기 위해서 최소를 버리자! Greedy한 사고

들어가며

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

가격(p)과 날짜(d)가 N개의 줄로 주어진다. 날짜안에 도착하여 강연을 하면 해당하는 가격을 받을 수 있는데, 그 가격의 합의 최대를 정답으로 출력하면 된다.

본문으로

처음 문제를 읽었을 때는 정렬만 잘 해서 출력하면 되겠는데..? 라는 생각이 먼저 든다. 그래서 날짜는 오름차순, 날짜가 같은 경우 가격이 높은순으로 정렬해서, 날짜별로 한개씩(이미 그 날짜의 최대 가격이 저장되어 있도록 정렬했으니!)만 뽑는 흐름으로 아래와 같이 출력했다.

public class Main {

    static class Lecture {
        int price;
        int day;

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


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Lecture> list = new ArrayList<>();
        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());
            list.add(new Lecture(price, day));
        }

        list.sort((o1, o2) -> {
            if (o1.day == o2.day) {
                return o2.price - o1.price;
            } else {
                return o1.day - o2.day;
            }
        });

        int ret = 0;
        int day = list.get(0).day;
        ret += list.get(0).price;
        for (int i = 1; i < list.size(); i++) {
            if (day != list.get(i).day) {
                ret += list.get(i).price;
                day = list.get(i).day;
            }
        }

        System.out.println(ret);
    }
}

문제에서 제공해주는 예제는 통과하는데, 자꾸 틀린다..

무슨 반례가 있는거지..? 내 코드는 아래와 같은 예제를 해결하지 못한다. 날짜마자 최대인 것을 한개씩 고르고 있기 때문에 1일에는 3, 2일에는 5를 골라서 8을 출력한다. 하지만 사실은 이틀안에만 도착하면 되는 것이기에 2일에 있는 4,5를 고르면 가장 많이 벌 수 있지 않겠는가!!!

2 1

3 1

4 2 

5 2

정답 : 9

내 코드 출력 : 8

---

근데 정렬된 순서대로 보면서.. 최대들만 고르게끔 설계하는 게 너무너무 어려웠다. 애초에 정렬된 순서대로 본다면 아까 위의 예제에서는 1일일때 3을 선택할 수 밖에 없지 않은가...? 결론은 이러한 그리디의 원하는 흐름을 제어하기 위해서 최소를 줄여서 최대들만 남기자! 라는 생각으로 좁혀진다. 최소를 줄이기엔 최소힙이 적합했다.

최소힙, 최대힙은 우선순위큐로 많이 구현한다. 그래서 아래와 같은 코드를 정답으로 제출했다.

public class Main {

    static class Lecture {
        int day;
        int price;

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Lecture> list = new ArrayList<>();
        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());
            list.add(new Lecture(day, price));
        }

        list.sort((o1, o2) -> {
            return o1.day - o2.day;
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            pq.add(list.get(i).price);
            if (pq.size() > list.get(i).day) {
                pq.poll();
            }
        }
        int ret = 0;
        while (!pq.isEmpty()) {
            ret += pq.poll();
        }

        System.out.println(ret);
    }
}

---

아래의 로직이 이 문제의 핵심이다. 우선 day 오름차순으로 정렬된 Lecture 리스트의 원소를 앞에서부터 한개씩 우선순위 큐에 넣으면서, 큐의 사이즈를 날짜의 경계선으로 이용한다. (이 아이디어를 처음 봤을때, 정말 놀랐다...) 그래서 만약 큐의 사이즈가 현재 수업의 날짜보다 크다면 큐에 저장되어 있는 최소 가격을 pop한다. 즉 최소가격이 pop되면서 2일 했을때는 pq에 두개의 가격이, 10일 했을때는 pq에 10개의 가격이 있을 것이다.

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            pq.add(list.get(i).price);
            if (pq.size() > list.get(i).day) {
                pq.poll();
            }
        }

위의 코드 때문에 아래와 같은 인풋이 들어왔을때 주석과 같은 흐름으로 최소 가격이 빠지면서, pq에는 최대 가격들만 남아있을 것이다.

// input
2 1
3 1
4 2 
5 2

// 1일차 (list.get(i).day == 1)
2 1

// 2일차 (list.get(i).day == 1)
3 1

// 3일차 (list.get(i).day == 2)
3 1
4 2

// 4일차 (list.get(i).day == 2)
4 2
5 2

마무리하며

이렇게 최대를 만들기 위해 우선순위큐(최소힙)로 최소를 제외시키며 최대값을 보장하는 방식은 처음 풀어봤다! 정말 괜찮고 문제에 어울리는 그리디한 방식이라고 생각한다.

 

최근 그리디한 문제를 풀고 있는데 여러가지 방법을 사고해보며, 최적의 부분해를 찾을 수 있는 방법을 떠올리는 그 흐름이 솔직히 너무 어렵다. 그래도 이 풀이 괜찮아보이는데..? 하면서 접근하다가 아니면 폐기하고... 다시 해볼만한 풀이 들고 도전해보고.. 하는 방식이 정말 문제를 요리하는 느낌이 난다! 그리디는 정말정말 연습 많이 해봐야하는 것 같다.

 

어떤 곳에서 그리디는 우디르급 태세 전환이라는 말을 들었었는데, 정말 맞는 말이었다.. 빠른 태세 전환으로 맞는 부분 최적해를 찾아가는 여행...  꾸준히 연습하자 🔥