백준 17503 "맥주 축제" (JAVA)

🔍 문제링크

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

문제 요약

• N일 동안 서로 다른 N개의 맥주를 마셔야 함.
• 맥주의 선호도 합이 M 이상이어야 함.
• 도수가 간 레벨보다 높으면 마실 수 없음.
• 가능한 도수의 최솟값을 출력.
•  

---

🛠 풀이 및 알고리즘

1. 맥주 리스트를 도수 기준으로 오름차순 정렬
   • 도수가 낮은 맥주부터 선택하여 조건을 만족하는지 확인.
2. 우선순위 큐(PriorityQueue) 활용
   • N개의 맥주를 유지하며, 가장 낮은 선호도를 가진 맥주는 제거.
   • PriorityQueue<Integer>에 맥주 선호도(prefer)를 저장하여 최소 선호도를 빠르게 제거.
3. 도수를 하나씩 증가시키며 조건을 만족하는지 확인
   • 현재 도수까지 마실 수 있는 맥주들 중에서 N개를 선택.
   • N개를 선택한 후, 선호도 합이 M 이상인지 체크.
   • 조건을 만족하면 현재 도수가 가능한 최솟값.

---

💡 코드

import java.util.*;

public class Baekjoon_17503 {

    static class Beer {
        int prefer, alcohol;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 마셔야 하는 맥주 수
        int m = sc.nextInt(); // 선호도 최소 합
        int k = sc.nextInt(); // 맥주 종류
        List<Beer> beers = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            beers.add(new Beer(sc.nextInt(), sc.nextInt()));
        }

        // 1. 도수(alcohol) 기준으로 오름차순 정렬 (도수가 같다면 선호도 큰 순)
        beers.sort((a, b) -> a.alcohol == b.alcohol ? b.prefer - a.prefer : a.alcohol - b.alcohol);

        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소 힙 (선호도)
        int sum = 0, ans = -1;

        // 2. 도수가 낮은 순서대로 맥주를 선택
        for (Beer beer : beers) {
            pq.add(beer.prefer);
            sum += beer.prefer;

            // 3. N개 초과하면 가장 낮은 선호도 제거
            if (pq.size() > n) {
                sum -= pq.poll();
            }

            // 4. 정확히 N개를 선택했으며, 선호도 합이 M 이상이면 도수 기록 후 종료
            if (pq.size() == n && sum >= m) {
                ans = beer.alcohol;
                break;
            }
        }

        System.out.println(ans);
    }
}

---

🏆 시간 복잡도 분석

• 맥주 정렬: O(K log K)
• 우선순위 큐 관리: O(K log N)
• 전체 시간 복잡도: O(K log K + K log N), 최대 10^5 log 10^5 정도로 충분히 가능.