백준 - Yonsei TOTO ( 12018번, JAVA )

Greedy ( https://www.acmicpc.net/problem/12018 )

풀이

• 먼저 최소한의 마일리지를 사용할 최소마일리지 배열, 최소한의 마일리지를 구할 마일리지 배열을 만들었다.
• 만약 수강신청인원 < 수강신청할 수 있는 인원인 경우는 최소마일리지에 1을 저장
• 만약 수강신청인원 >= 수강신청할 수 있는 인원인 경우는 p-l 번쨰 마일리를 저장
• 최소한의 마일리지이므로 정렬 후 총 마일리지 m을 벗어나지 않는 경우에 answer를 증가

package problem_solving.greedy;

import java.util.Arrays;
import java.util.Scanner;

public class BaekJoon_12018 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		int answer= 0 ; 
		int [] minMil = new int [n]; 
		int index = 0 ; 
		while(n--> 0) {
			int p = Integer.parseInt(sc.next());
			int l = Integer.parseInt(sc.next());
			
			int [] miles = new int[p];
			
			for(int i = 0 ; i <miles.length;i++) {
				miles[i] = Integer.parseInt(sc.next());
			}
			
			Arrays.sort(miles);
			
			if( l > p) {
				minMil[index++]++;
			} else {
				minMil[index++]+=miles[p-l];
			}
			
		}
		
		Arrays.sort(minMil);
		int sum = 0 ; 
		for(int i = 0 ; i < minMil.length; i++) {
			sum+=minMil[i];
			if( sum > m) {
				break;
			}else {
				answer++;
			}
			
		}
		
		System.out.println(answer);
		sc.close();
	}

}