백준 17503번
https://www.acmicpc.net/problem/17503

문제

---

생각하기

---

• 그리디

• 우선순위 큐

동작

도수는 낮으면서 선호도는 높은 순으로 정렬한다.

        @Override
        public int compareTo(Beer o) {
            // 도수는 낮고 선호도는 높고
            if (abv == o.abv) {
                return o.prefer - prefer;
            }

            return abv - o.abv;
        }

        int preferSum = 0; // 선호도 합
        PriorityQueue<Integer> temp = new PriorityQueue<>();

        // 선호도 값
        int max = 1;

        while (!pque.isEmpty()) {
            Beer cur = pque.poll();

            preferSum += cur.prefer;
            temp.offer(cur.prefer);
            max = Math.max(max, cur.abv);

            if (temp.size() == N) {
                // 선호도가 가장 낮은 맥주를 버린다.

                if (preferSum < M) {
                    preferSum -= temp.poll();
                } else {
                    break;
                }
            }
        }

이제 선호도의 합을 구하는데, 선호도를 PriorityQueue로 관리한다.

temp 우선순위 큐의 개수가 N가 되면 preferSum이 M을 초과하는지 보고

M을 초과하지 않는다면 가장 낮은 선호도를 가진 맥주를 버린다. 이런식으로 순회하면서 M의 합을 넘기는 첫 번째에서 break를 한다.

그럼 답을 구할 수 있다.

결과

코드

---

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M, K;
    private static PriorityQueue<Beer> pque;

    private static class Beer implements Comparable<Beer> {
        int prefer;
        int abv;

        private Beer(int prefer, int abv) {
            this.prefer = prefer;
            this.abv = abv;
        }

        @Override
        public int compareTo(Beer o) {
            // 도수는 낮고 선호도는 높고
            if (abv == o.abv) {
                return o.prefer - prefer;
            }

            return abv - o.abv;
        }
    } // End of Beer class

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int preferSum = 0; // 선호도 합
        PriorityQueue<Integer> temp = new PriorityQueue<>();

        // 선호도 값
        int max = 1;

        while (!pque.isEmpty()) {
            Beer cur = pque.poll();

            preferSum += cur.prefer;
            temp.offer(cur.prefer);
            max = Math.max(max, cur.abv);

            if (temp.size() == N) {
                // 선호도가 가장 낮은 맥주를 버린다.

                if (preferSum < M) {
                    preferSum -= temp.poll();
                } else {
                    break;
                }
            }
        }

        if (preferSum < M) {
            sb.append(-1);
        } else {
            sb.append(max);
        }

        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        pque = new PriorityQueue<>();
        for (int i = 1; i <= K; i++) {
            st = new StringTokenizer(br.readLine());
            pque.offer(new Beer(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
    } // End of input()
} // End of Main class