[백준 / Java] 12018 Yonsei_TOTO

 

 

12018 Yonsei TOTO

링크

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

 

문제

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

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

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

 

입력

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

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

 

출력

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

 

예제 입력 1 

5 76
5 4 
36 25 1 36 36
4 4
30 24 25 20
6 4
36 36 36 36 36 36
2 4
3 7
5 4
27 15 26 8 14

 

예제 출력 1 

4

 

풀이 

1. BufferedReader와 StringTokenizer를 이용하여 과목 수(N), 주어진 마일리지(M), 각 과목에 신청한 사람의 수(P), 수강인원(L), 마일리지를 입력받음.

2. 신청한 사람의 수와 수강 인원에 관계에 따라서 조건문 실행

        - 만약 신청 인원이 수강 인원보다 많거나 같을 때, 각 사람의 마일리지를 정렬 -> P-L번째 마일리지 값을 해당 과목에 할당함 (마일리지가 같다면 성준이에게 우선 순위)

        - 만약 신청 인원이 수강 인원보다 작을 때,  최소 마일리지인 1을 할당

3. 과목에 할당해야하는 마일리지가 작은 값부터 듣는 것이 최대 과목을 들을 수 있는 경우 -> 각 과목에 할당할 마일리지를 정렬 

4. 반복문과 조건문을 통하여 최대 과목을 구함

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class BJ12018_Yonsei_TOTO {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);

		int n = Integer.parseInt(st.nextToken()); // 과목 수 N
		int m = Integer.parseInt(st.nextToken()); // 주어진 마일리지 M
		int[] mileage = new int[n]; // 각 과목을 듣기 위한 최소 마일리지의 배열

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			int p = Integer.parseInt(st.nextToken()); // 각 과목에 신청한 사람의 수 P
			int l = Integer.parseInt(st.nextToken()); // 수강인원 L

			int[] tmp_mileage = new int[p]; // 해당 과목에서 각 사람이 마일리지를 얼마나 넣었는지 담은 배열
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < p; j++) {
				tmp_mileage[j] = Integer.parseInt(st.nextToken());
			}

			if (p >= l) { // 만약 신청 인원이 수강 인원보다 많을 때
				Arrays.sort(tmp_mileage); // 각 사람의 마일리지를 정렬
				mileage[i] = tmp_mileage[p - l]; // P - L 번째 값을 할당함 (마일리지가 같다면 성준이에게 우선순위)
			} else { // 만약 신청 인원이 수강 인원보다 적을 때
				mileage[i] = 1; // 최소 마일리지인 1을 할당함
			}
		}
		System.out.println(countMaxSubject(mileage, m));
	}

	public static int countMaxSubject(int[] mileage, int m) {
		Arrays.sort(mileage);
		int sum = 0, count = 0;
		for (int i = 0; i < mileage.length; i++) {
			sum += mileage[i];
			if (sum > m) {
				break;
			}
			count++;
		}
		return count;
	}
}