[Algorithm] 99클럽 코테 스터디 18일차 TIL | 백준_맥주 축제(17503번)

📝문제

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

 

💡풀이

선호도의 합이 M이상이고

마신 맥주가 N개를 만족해야한다.

 

1) 맥주 도수 레벨을 기준으로 배열을 오름차순하고

2) 우선순위 큐에 선호도 기준으로 오름차순한다.

3) 배열을 돌려 차례대로 우선순위 큐에 저장하고

4) 큐 사이즈가 N개가 되면 큐에 들어간 선호도 합을 계산한다.

4-1) 선호도 합이 M이상이면 현재 맥주의 도수 레벨이 정답이 되므로 반복문을 빠져나온다.

4-2) 선호도 합이 M 미만이면 다시 3)으로 돌아가서 가장 작은 선호도를 가진 맥주를 큐에서 빼낸다.

M 미만이면 바로 큐에서 빼지 않는 이유: 다음 선호도가 현재 최소 선호도보다 작을 수 있음!

import java.util.*;
import java.io.*;

class Main {
    static int[][] beer;
    static int N, M;

    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());//기간
        M = Integer.parseInt(st.nextToken());//선호도 합
        int K = Integer.parseInt(st.nextToken());//맥주 종류

        beer = new int[K][2];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            beer[i][0] = Integer.parseInt(st.nextToken());//선호도
            beer[i][1] = Integer.parseInt(st.nextToken());//도수레벨
        }

        Arrays.sort(beer, Comparator.comparingInt(a -> a[1])); //1) 도수 기준으로 오름차순

        PriorityQueue<Integer> pq = new PriorityQueue<>(); //2) 선호도 기준으로 오름차순
        int sum = 0; //선호도 합
        int answer = -1;
        for (int[] a : beer) {
            int like = a[0];
            int alcohol = a[1];

            pq.add(like);
            sum += like;

            if (pq.size() > N) {
                sum -= pq.poll();
            }
            if (pq.size() == N) {
                if (sum >= M) { //선호도 합이 M이상 되어야 함
                    answer = alcohol;
                    break;
                }
            }
        }
        System.out.println(answer);
    }
}

 

🤔Review

문제가 선호도 합이 M일때를 찾는 줄 알고 한참 헤맸다.. 문제 좀 제대로 읽자ㅜㅠ^^