백준 - 12018

[Silver III] Yonsei TOTO - 12018

문제 링크

성능 요약

메모리: 25096 KB, 시간: 340 ms

분류

그리디 알고리즘, 정렬

문제 설명

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.

성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.

그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

입력

첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 P_i과 과목의 수강인원 L_i이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ P_i ≤100, 1 ≤ L_i ≤ 100)

(단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)

출력

첫째 줄에 주어진 마일리지로 최대로 들을 수 있는 과목 개수를 출력한다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 과목 수
        int m = sc.nextInt(); // 주어진 마일리지
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            int p = sc.nextInt(); // 과목을 신청한 사람 수
            int l = sc.nextInt(); // 과목의 수강인원
            int[] mileage = new int[p]; // 각 사람이 넣은 마일리지
            for (int j = 0; j < p; j++) {
                mileage[j] = sc.nextInt();
            }
            if (p < l) { // 과목의 수강인원보다 신청자가 적을 때
                arr[i] = 1; // 내가 사용할 마일리지
            } else {
                Arrays.sort(mileage);
                arr[i] = mileage[p - l]; // 마일리지가 같으면 성준이에게 우선순위가 있기 때문
            }
        }
        Arrays.sort(arr);
        int maxCount = 0; // 최대로 들을 수 있는 과목 개수
        for (int i = 0; i < n; i++) {
            if (arr[i] > m) { // 어떤 과목 신청에 쓰이는 마일리지가 내게 주어진 마일리지보다 크면 멈춤
                break;
            }
            m -= arr[i]; // 내 마일리지 - 사용한 마일리지
            maxCount++;
        }
        System.out.println(maxCount);
    }
}