링크

Yonsei TOTO-12018

문제

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

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

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

입력

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

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

출력

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

풀이

처음에 접근하였을 때 2차원 배열로 접근하였다. 하지만 생각해보니 2차원 배열로 접근도 가능하지만 정렬을 하는데 조금 더 복잡함을 느꼈다.
그렇기 때문에 과목을 얻기 위한 최소 마일리지 배열인 minimum배열과
과목에 들어가있는 마일리지 배열인 arr배열을 잡아주었다.

1. 수강신청 인원이 최대 인원 수 보다 작으면 그냥 1점 사용
2. 그렇지 않을때는 점수들을 내림차순으로 정렬한 뒤 최대 인원수-1 의 인덱스값을 뽑아내면 그게 최소로 필요한 마일리지
3. 이런식으로 그 과목에 필요한 마일리지 최솟값을 배열에 담고 다시 오름차순 정렬
4. 내 마일리지 점수에서 배열에 든 마일리지 값을 빼가면서 과목수 ++

Code

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

public class Main {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		int n=Integer.parseInt(st.nextToken()); //과목 수
		int m=Integer.parseInt(st.nextToken()); //마일리지
		int[] minimum=new int[n]; // 과목을 얻기 위한 최소 마일리지 배열
		
		for(int i=0; i<n; i++)
		{
			StringTokenizer st2=new StringTokenizer(br.readLine());
			int people=Integer.parseInt(st2.nextToken()); //과목 신청한 사람 수
			int maximum=Integer.parseInt(st2.nextToken()); //최대 수강인원
			Integer arr[]=new Integer[people];
			
			StringTokenizer st3=new StringTokenizer(br.readLine());
			
			for(int j=0; j<people; j++)
				arr[j]=Integer.parseInt(st3.nextToken());
			
			Arrays.sort(arr, Collections.reverseOrder());
			
			if(maximum >people)
				minimum[i]=1;
			else
			{
				minimum[i]=arr[maximum-1];
			}
		}
		
		Arrays.sort(minimum);
		int result=0;
		for(int i=0; i<minimum.length; i++)
		{
			if(m>=minimum[i])
			{
				m-=minimum[i];
				result++;
			}
		}
		
		System.out.println(result);
	}
}