[백준/BOJ] 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)

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

출력

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

해설

PriorityQueue를 이용하여 최소 마일리지를 담는다.

최소 마일리지를 구할 때는 PriorityQueue를 내림차순으로 선언하였다.

 

성준이는 내림차순의 우선순위 큐에 마일리지를 담아 l번쨰의 마일리지만큼 내면 된다.

(마일리지가 같을 경우, 성준이한테 우선순위가 주어지기 때문이다.)

만약 신청인원 >= 수강인원이라면 성준이는 마일리지를 1만 내어도 수강신청에 성공할 수 있다.

 

과목 당 필요한 최소 마일리지를 구하였다면 현재 성준이가 가지고 있는 마일리지 안에서 몇개의 과목을 신청할 수 있는지 세어보면 된다.

소스 코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    var m = st.nextToken().toInt()
    val que = PriorityQueue<Int>()
    repeat(n) {
        st = StringTokenizer(readLine())
        val p = st.nextToken().toInt()
        val l = st.nextToken().toInt()
        st = StringTokenizer(readLine())
        val other = PriorityQueue<Int>(Collections.reverseOrder())
        repeat(p) { other.add(st.nextToken().toInt()) }
        if(p >= l) {
            repeat(l-1) { other.poll() }
            que.add(other.poll())
        }
        else que.add(1)
    }
    var cnt = 0
    while(!que.isEmpty()) {
        var mile = que.poll()
        if(m >= mile) {
            m -= mile
            cnt++
        }
        else break
    }
    println(cnt)
}