최대한 많은 과목을 수강하기 위해서는 각 과목을 최소로 들을수 있는 마일리지부터 신청
해야한다.
그러기 위해서는 각 과목에 신청된 마일리지를 내림차순 정렬
후 수강가능 인원의 범위에 있는 마일리지 중 가장 작은 마일리지를 선택
한다.(마일리지가 같으면 성준이에게 우선순위가 있다.)
각 과목을 듣기 위한 최소 마일리지를 선택했다면 이를 오름차순 정렬하여 주어진 마일리지로 신청할 수 있는 최대 과목 수를 구하면 된다
.
public class YonseiTOTO {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
//과목 수
int N = Integer.parseInt(st.nextToken());
//주어진 마일리지
int M = Integer.parseInt(st.nextToken());
//각 과목을 듣기 위한 최소 마일리지
int[] myMileage = new int[N];
//각 과목의 신청한 마일리지
List<Integer>[] mileageOfSubject = new List[N];
//[0] : 신청 인원, [1] : 강 가능 인원
int[][] subjectInfo = new int[N][2];
for (int i = 0; i < N; i++) {
mileageOfSubject[i] = new ArrayList<>();
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int P = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(), " ");
subjectInfo[i] = new int[] {P, L};
for (int l = 0; l < P; l++) {
mileageOfSubject[i].add(Integer.parseInt(st.nextToken()));
}
}
for (int i = 0; i < N; i++) {
List<Integer> mileage = mileageOfSubject[i];
//해당 과목에 신청된 마일리지 내림차순 정렬
mileage.sort(Collections.reverseOrder());
int p = subjectInfo[i][0];
int l = subjectInfo[i][1];
//신청한 인원이 신청가능인원보다 같거나 많다면 신청가능인원의 마지막에 있는 마일리지 값 저장
if (p >= l) {
int limitStudentsMileage = mileage.get(l-1);
myMileage[i] = limitStudentsMileage;
}
//신청한 인원이 적다면 최소 마일리지 1 저장.
else {
myMileage[i] = 1;
}
}
//과목을 신청할수 있는 최소 마일리지를 오름차순 정렬
Arrays.sort(myMileage);
int count = 0;
int sum = 0;
//주어진 마일리지 내에서 신청가능한 과목 개수
for (int i = 0; i < N; i++) {
sum += myMileage[i];
if (sum > M)
break;
count++;
}
bw.write(String.valueOf(count));
bw.flush();
bw.close();
}
}