[BOJ] 12018. Yonsei TOTO - JAVA 자바

12018번: Yonsei TOTO

💡 Priority Queue

 

가장 적은 마일리지로 가장 많은 과목을 수강하기 위해서는 모든 과목에 사용해야하는 최소의 마일리지를 구한 후, 가장 적게 드는 과목부터 주어진 마일리지를 초과하지 않도록 하나씩 더하면 풀 수 있는 문제이다.

 

1. 각 과목에 신청한 마일리지들을 높은 우선순위 큐에 넣어준다.
2. (수강인원-1)이 될 때까지 마일리지가 큰 순서대로 poll 해준다. 한 자리는 성준이자리
    2-1. 신청한 사람 수보다 수강인원이 많으면 1 마일리지를 사용해도 수강할 수 있으므로 1을 return

3. 2번 방식으로 구한 특정 과목을 수강하기 위해 필요한 최소 마일리지를 다시 우선순위 큐에 넣어준다.
4. 모든 과목을 반복하며 최소 마일리지를 구한 후 우선순위 큐에 넣어준다.
5. 최소 마일리지들이 들어간 낮은 우선순위 큐를 poll 하며 내가 들을 과목 수++ , 사용한 마일리지 합 계산
6. 마일리지를 초과하면 stop

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public int useMileage(PriorityQueue<Integer> queue, int limit) {
        int count = 0;
        while (count < limit - 1 && !queue.isEmpty()) {
            queue.poll();
            count++;
        }

        if (queue.isEmpty()) {
            return 1;
        } else {
            return queue.poll();
        }

    }

    public static void main(String[] args) throws IOException {
        Main M = new Main();
        int n, m, p, l;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken()); // 과목 수
        m = Integer.parseInt(st.nextToken()); // 총 마일리지

        PriorityQueue<Integer> mileage = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            p = Integer.parseInt(st.nextToken()); // 신청한 사람 수
            l = Integer.parseInt(st.nextToken()); // 과목의 수강인원

            PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < p; j++) {
                queue.add(Integer.parseInt(st.nextToken()));
            }

            // 필요한 최소 마일리지 구한 후 mileage 배열에 추가
            if (p < l) {
                mileage.add(1);
            } else {
                mileage.add(M.useMileage(queue, l));
            }
        }

        int sum = 0, result = 0;
        while (!mileage.isEmpty()) {
            sum += mileage.poll();

            if (sum > m) {
                System.out.println(result);
                return;
            }
            result++;
        }
        System.out.println(n);
    }
}