백준 12018. Yonsei TOTO(JAVA)

○ 문제 요약

성준이가 현재 가진 마일리지로 최대 수강 신청할 수 있는 강의가 몇 개인지 구하자.

○ 문제 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {

        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[] arr = new int[n];
        int cnt = 0;

        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());
            if(P >= L){
                int[] subArr = new int[P];
                for(int j = 0 ; j < P; j++) subArr[j] = Integer.parseInt(st.nextToken());
                Arrays.sort(subArr);
                arr[i] = subArr[P - L];
            }else{
                arr[i] = 1;
            }
        }

        Arrays.sort(arr);
        for(int i = 0 ; i < arr.length; i++){
          if(arr[i] > m) break;
          m -= arr[i];
          cnt++;
        }
        System.out.println(cnt);
    }
}

첫 번째로 해야할 것이 수강 인원과 수강 신청인원을 비교하는 것이다. 

 

수강 신청인원이 수강 인원보다 적다면 최소한의 마일리지만 사용해야 효율적으로 마일리지를 사용할 수 있기 때문이다.

반면에 수강 인원보다 수강 신청 인원이 많다면 각 인원의 마일리지를 정렬해서 이 강의를 신청하기 위한 최소 마일리지를 알아낼 수 있다.

 

두 번째는 앞에서 구한 각 강의의 최소 마일리지를 정렬해서 수강 신청할 수 있는 강의의 수를 알려주면 된다.

 

정렬한 마일리지를 차례로 더해주는면 되는데 이때, 성준이가 가진 마일리지보다 커지는 순간 연산을 멈추고 현재까지 더한 강의의 수를 출력해주면 된다. 

 

 

 

○ 결과