백준 9576 책 나눠주기

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

1~N까지 번호가 적인 책 N권과 a..b 범위의 책을 받으려는 M명의 학생들이 주어진다.

책을 줄 수 있는 최대 학생 수를 출력하는 문제이다.

경험치를 얻게 된 꽤나 헤메게 만든 문제이다.

처음 생각했던 것은, 구간의 길이의 오름차순으로 (같으면 시작 번호 오름차순)정렬한 다음 앞번호부터 책을 주는 방법이었다.

범위가 짧은 구간들 중, 시작 번호가 작은 학생들 먼저 앞번호 책을 준다면 되려나 생각했었다.

하지만 (1 2), (2 3), (3 4), (1 3)같은 케이스라면 모두 책을 줄 수 있음에도 1~3번 책만 주게 된다.

그래서 다음 생각한 방법은 구간의 끝(b)을 기준으로 내림차순 정렬한 뒤(같으면 a 내림차순) 뒷번호부터 책을 주는 방법이었다.

(1 2), (2 3), (3 4), (1 3) 같은 케이스를 (3 4) (2 3) (1 3) (1 2)로 정렬해서 1~4 까지 모든 책을 줄 수 있어 보였다.

구간이 끝이 b인 범위들에서, a가 큰(구간이 짧은) 순서대로 준다면 될 것 같다고 생각했다.

하지만 이 방법에도 흠이 있었다.

(2 5) (2 5) (2 5) (4 4) (1 1)같은 케이스가 주어지면, (4 4)에게 4번 책을 줄 수가 없었다.

그래서 마지막으로 a를 기준으로 내림차순(같으면 b 내림차순)으로 정렬하고 뒷번호부터 책을 주는 방법을 사용했다.

현재 학생 이후의 학생들은 현재 학생의 a값보다 작거나 같은 (같다면 b도 작거나 같은) 값을 가졌다는 것을 보장해서, 뒷번호의 책부터 빌려 준다면 될 것 같다 생각했다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val T = readLine().toInt()
    val sb = StringBuilder()

    for(case in 1..T){
        val (N, M) = readLine().split(' ').map{it.toInt()}

        val students = Array(M){
            val (a, b) = readLine().split(' ').map{it.toInt()}
            Pair(a, b)
        }.sortedWith{s1, s2 ->
            if(s1.first == s2.first) s2.second - s1.second
            else s2.first - s1.first
        }

        var answer = 0
        val bookCheck = BooleanArray(N + 1){false}

        for(st in students){
            if(!bookCheck[st.second]){
                bookCheck[st.second] = true
                answer++
            }else{
                for(i in st.second downTo st.first){
                    if(!bookCheck[i]){
                        bookCheck[i] = true
                        answer++
                        break
                    }
                }
            }
        }

        sb.append("$answer\n")
    }

    print(sb.toString())
}

될 것 같은데 자꾸 예외적인 케이스를 발견해서 헷갈렸던 문제였다.

그래도 뭔가 그리디 같은 문제에 a에서 b까지 범위가 있다면
(오름, 오름), (오름, 내림), (내림, 오름), (내림, 내림) 4가지 범위 정렬중 실마리가 있을 것 같다는 느낌을 받았다.