[JAVA] 1202 - 보석 도둑 💛2 : 열받아서 작성하는 그리디한 문제

들어가며

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

 

N개의 줄에 보석의 무게와 가격이 주어지고, K개의 줄에 가방에 무게가 주어진다. 가방에는 하나의 보석만 담을 수 있는데, 그 중 담을 수 있는 보석 가격의 합의 최대를 정답으로 출력하면 된다. 무게가 크더라도 값이 싼 보석이 있을 수 있기에 잘 선택해야 하는 그리디 문제다.

본문으로

결론 먼저 말하자면 이 문제는 삽질을 굉장히 많이 했다...ㅋㅋ 약간 졸린 상태에서 풀어서, 이거는 내일 아침에 다시 풀면 풀리겠군! 하고 자고 다시 풀어봤는데도 계속 틀렸다..

틀렸습니다.틀렸습니다.틀렸습니다.틀렸습니다.틀렸습니다.틀렸습니다.틀렸습니다.

반례가 도저히 떠오르지 않아, 질문 게시판에 반례의 도움을 받았다. 역시 나와 같은 부분에서 헷갈리는 분들이 많았나보다. 아래 로직이 가장 %가 많이 올라가다가 틀린 로직이다.

public class Main {

    static long N, K, ret;
    static List<Je> jeList;
    static List<Integer> bagList;

    static class Je {
        int weight;
        int price;

        Je(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        ret = 0;

        jeList = new ArrayList<>();
        bagList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer line = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(line.nextToken());
            int price = Integer.parseInt(line.nextToken());
            jeList.add(new Je(weight, price));
        }

        for (int i = 0; i < K; i++) {
            bagList.add(Integer.parseInt(br.readLine()));
        }

        jeList.sort((o1, o2) -> {
            if (o1.weight == o2.weight) {
                return o2.price - o1.price;
            }
            return o1.weight - o2.weight;
        });

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

        int bagCnt = 0;
        int jeCnt = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            return o2 - o1;
        });
        while (bagCnt < bagList.size() && jeCnt < jeList.size()) {
            if (jeList.get(jeCnt).weight > bagList.get(bagCnt)) {
                bagCnt++;
                if (!pq.isEmpty()) {
                    ret += pq.poll();
                }
                continue;
            }
            pq.add(jeList.get(jeCnt).price);
            if (pq.size() > bagCnt + 1) {
                ret += pq.poll();
            }
            jeCnt++;
        }
        if (bagCnt != bagList.size() && jeCnt != jeList.size()) {
            ret += pq.poll();
        }
        System.out.println(ret);
    }
}

보석을 무게 기준으로 오름차순으로 진행하되, 무게가 같을 경우 가격 내림차순을 한다. 그리고 가방은 오름차순으로 정렬하여, 가방 무게에 맞는 보석들을 싹 다 우선순위 큐에 넣고 한개 뽑으면 다음 가방으로 넘어간다. 처음 아이디어 자체는 맞았는데, 사실 구현이 너무 어려웠다.

위의 로직은 몇가지 반례에서 가방이 끝까지 처리가 안되거나, 가방당 1개가 들어간다는 보장이 깨진다...(틀리고 수정하고 틀리고 수정하다 보니 인덱스 관련하여 로직이 많이 어지러워졌다..) 이 문제는 대부분 아래의 반례로 문제를 해결 할 수 있을 것이다!

2 2
9 9
9 1
9
6
//정답
9

3 3
20 12
0 20
16 16
17
14
7
// 정답
48

---

 위의 반례를 기준으로 아래와 같은 코드를 정답을 제출했다! 사실 아이디어는 똑같다. 현재 가방 무게 안에 넣을 수 있는 보석 우선순위큐에 다 넣고, 그중 하나 뽑으면 다음 가방으로 넘어가기. 

public class Main {

    static long N, K, ret;
    static List<Je> jeList;
    static List<Integer> bagList;

    static class Je {
        int weight;
        int price;

        Je(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        ret = 0;

        jeList = new ArrayList<>();
        bagList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer line = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(line.nextToken());
            int price = Integer.parseInt(line.nextToken());
            jeList.add(new Je(weight, price));
        }

        for (int i = 0; i < K; i++) {
            bagList.add(Integer.parseInt(br.readLine()));
        }

        jeList.sort((o1, o2) -> {
            if (o1.weight == o2.weight) {
                return o2.price - o1.price;
            }
            return o1.weight - o2.weight;
        });

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

        int jeCnt = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            return o2 - o1;
        });

        for (int i = 0; i < K; i++) {
            while (jeCnt < N && jeList.get(jeCnt).weight <= bagList.get(i)) {
                pq.add(jeList.get(jeCnt).price);
                jeCnt++;
            }
            if (!pq.isEmpty()) {
                ret += pq.poll();
            }
        }
        System.out.println(ret);
    }
}

마무리하며

그리디는 "이 생각이 맞을까?" 하고 접근을 했다가 아닌거 같으면 바로 다른 풀이로 접근하는 생각의 전환이 중요한데, 그 과정에서 풀이가 많이 더러워지는 것 같다. 그 전에 썻던 로직이 아까워서 거기서 수정을 하려고 계속 노력하다보니 설계 자체가 불가능한 상황까지 가버린다. 실제 시험에서 이런 상황이 발생한다면, 사실 그 문제는 구조적으로 빠른 포기를 해야하지 않나 싶다... 
결국 문제를 보고 최적의 부분해를 찾아낼 수 있는 감각을 키우는 게 중요한 것 같다!! 그럴수록 반복적인 연습이 답이다. 가보자🔥