BOJ - 12018 Yonsei TOTO

Problem

---

Solve

최대한 많은 과목을 수강하기 위해서는 각 과목을 최소로 들을수 있는 마일리지부터 신청해야한다.

그러기 위해서는 각 과목에 신청된 마일리지를 내림차순 정렬 후 수강가능 인원의 범위에 있는 마일리지 중 가장 작은 마일리지를 선택한다.(마일리지가 같으면 성준이에게 우선순위가 있다.)

각 과목을 듣기 위한 최소 마일리지를 선택했다면 이를 오름차순 정렬하여 주어진 마일리지로 신청할 수 있는 최대 과목 수를 구하면 된다.

---

Code

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();
	}
}

---

Result

---

Reference