[백준] 12018번 : Yonsei TOTO

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

12018번: Yonsei TOTO

 

문제

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

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

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

 

입력

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

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

 

출력

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

 

---

소스코드

import java.util.*;
import java.io.*;

class Main {

    public static void main(String[] args) throws Exception {
        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());
        List<Integer> al1 = 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());
            List<Integer> al2 = new ArrayList<>();
            while (st.hasMoreTokens()) al2.add(Integer.parseInt(st.nextToken()));
            Collections.sort(al2, Collections.reverseOrder());

            if (al2.size() < l) al1.add(1);
            else al1.add(al2.get(l - 1));
        }

        int result = 0;
        Collections.sort(al1);
        for (Integer i : al1) {
            m -= i;
            if (m >= 0) result += 1;
            else break;
        }

        System.out.println(result);
    }
}

 

해결 방법

1. 과목마다 신청한 학생들의 마일리지를 내림차순 정렬한다.
2. 정렬된 값 중 수강인원에 들어갈 수 있는 최솟값을 구하여 List에 저장한다. 만약 과목을 신청한 학생보다 수강인원이 많다면 최솟값은 1이 된다.
3. List에는 과목마다 수강할 수 있는 최소 마일리지 값이 들어있다. 이를 오름차순 정렬하여 주어진 마일리지 값으로 최대한으로 들을 수 있는 과목의 수를 구한다.