BOJ 1931: 회의실 배정

문제

링크

solved.ac Gold V, Class 3, 에센셜

시도 1 (시간 초과)

풀이

먼저 예시를 보자.

1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

문제의 조건을 생각해보면, 먼저 회의의 끝나는 시간과 시작하는 시간이 같을 수 있으므로 문제를 구간별로 나눠볼 수 있다. 한번 예시를 구간별로 나눠보자. 먼저 (4, 5) 구간을 보자.

여기에서 가능한 회의의 수를 많게 하려면 어떻게 해야 할까? 4에서 끝나고 5가 비어 있는 회의를 선택하면, 5에서 시작하는 회의를 선택할 수 있는 반면 4와 5 모두 진행되는 회의는 1개밖에 선택할 수 없다. 따라서 어떤 구간 (n, n+1)에서는 끝나는 시간이 n인 회의를 선택하면 가장 많은 회의를 선택할 수 있다. 한번 이 방법을 적용해보자.

이렇게 선택한 회의는 0, 3, 7, 10번 회의로 총 4개이다. 이는 문제의 힌트에 적힌 회의와도 일치한다. 이 방법이 여러 상황에서 유효한지 검증해 보자. 예시에는 같은 시간에 끝나는 회의가 없었지만, 해당 상황에서도 유효한지 검증해보자.

위 방법을 사용하면 (1, 2) 구간에서 2개의 선택지가 있다. 어차피 둘 중 하나만 선택할 수 있고, 1번에서 끝나는 어떤 회의를 선택하든 그 뒤의 회의를 선택하는 것과는 상관이 없으므로 둘 중 아무 회의나 선택해도 총 개수에는 상관이 없다.

정리

• 모든 회의의 마지막 시간을 $t$라고 하고, 최소 시간 변수를 $m$(초깃값 0)이라고 하자. 회의 갯수를 $res$이라고 하자.
• 0..$t$까지 순서대로, 번호를 $n$이라 하고 $t$에서 끝나며 시작이 $m$ 이상인 회의 $i$를 선택한다. 회의가 있으면 $res$++하고, $m=n+1$한다.
• $n$을 출력한다.

구현

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val meetings = mutableListOf<Pair<Int, Int>>()

    (0 until nextInt()).forEach { _ -> meetings.add(nextInt() to nextInt()) }

    val t = meetings.maxOf { it.second }
    var m = 0
    var res = 0

    (0..t).forEach { n -> // 구간 (n, n+1)
        val i = meetings.indexOfFirst { it.second == n && it.first >= m }

        if (i == -1) return@forEach

        res++
        m = n + 1
    }

    println(res)
}

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val meetings = mutableListOf<Pair<Int, Int>>()

    (0 until nextInt()).forEach { _ -> meetings.add(nextInt() to nextInt()) }

    val t = meetings.maxOf { it.second }
    var m = 0
    var res = 0

    (0..t).forEach { n -> // 구간 (n, n+1)
        val i = meetings.indexOfFirst { it.second == n && it.first >= m }

        if (i == -1) return@forEach

        res++
        m = n + 1
    }

    println(res)
}

시도 2 (오답)

문제점과 개선 방안

위 풀이는 $O(tn)$이다(시간 초과). $m$은 계속 증가하므로 미리 회의가 끝나는 시간에 따라 정렬하면 끝나는 시간이 $n$ 이상인 회의를 리스트 순회 없이 찾을 수 있다. 따라서 시간 복잡도를 $O(n)$으로 줄일 수 있다. 예시를 보자.

이 예시는 이미 정렬되어 있다. 입력이 정렬되어 있다는 보장은 없으므로 정렬은 해야 한다.

먼저 0번째 회의는 4에서 끝나므로 $res$++, $m=4$.

이제 회의 시작이 $m$ 이상인 회의를 인덱스를 늘려가며 찾는다. 여기서는 3번 회의를 찾을 수 있다. $res$++, $m=7$. 계속 진행하면 7번 회의, 10번 회의를 찾을 수 있다. 따라서 $res$=4이다.

이는 앞선 방법과 같은 결과를 얻을 수 있으면서도(구간을 만족하는 회의를 찾는 대신, 정렬 후 회의가 속한 구간을 찾는 것으로 보면 같은 결과를 얻을 수 있음을 알 수 있다) 시간 복잡도가 $O(n)$이다.

그리디 알고리즘

이 방법은 그리디 알고리즘으로 볼 수 있다. 그리디 알고리즘은 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 방법이다[1]. 이 방법에서는 가장 빨리 끝나는 회의를 탐욕적으로 선택해나가며 최대 회의 수를 구하므로 그리디 알고리즘으로 볼 수 있다.

정리

• 회의 수를 $n$이라 하고, 회의 개수를 $res$, 최소 시간 변수를 $m$(초깃값 0)이라고 하자.
• 회의를 끝나는 시간에 따라 정렬한다.
• 0..$n$까지 순서대로, 회의 $i$의 시작과 끝을 각각 $a$, $b$라고 했을 때 $a \ge m$이면 $res$++, $m=b$한다.
• $res$를 출력한다.

구현

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val n = nextInt()
    val meetings = mutableListOf<Pair<Int, Int>>()

    (0 until n).forEach { _ -> meetings.add(nextInt() to nextInt()) }

    meetings.sortBy { it.second }

    var m = 0
    var res = 0

    (0 until n).forEach { i ->
        if (meetings[i].first /* a */ < m) return@forEach

        res++
        m = meetings[i].second /* b */
    }

    println(res)
}

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val n = nextInt()
    val meetings = mutableListOf<Pair<Int, Int>>()

    (0 until n).forEach { _ -> meetings.add(nextInt() to nextInt()) }

    meetings.sortBy { it.second }

    var m = 0
    var res = 0

    (0 until n).forEach { i ->
        if (meetings[i].first /* a */ < m) return@forEach

        res++
        m = meetings[i].second /* b */
    }

    println(res)
}

시도 3

문제점과 개선 방안

위 풀이에는 반례가 존재한다[2].

3
4 4
3 4
2 4

3
4 4
3 4
2 4

이는 (2, 4) 또는 (3, 4), (4, 4)를 선택하면 2개의 회의를 선택할 수 있다. 하지만 위 풀이는 1개의 회의만 선택한다. 이는 회의가 끝나는 시간이 같을 때 먼저 입력된 회의를 선택하기 때문이다. 이를 해결하기 위해 회의가 끝나는 시간이 같을 때 시작 시간을 기준으로 정렬해야 한다. Kotlin의 sortBy는 stable하므로, 먼저 시작 시간으로 정렬하고 끝나는 시간으로 정렬하면 끝나는 시간이 같을 때 시작 시간이 빠른 순으로 정렬된다.

구현

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val n = nextInt()
    val meetings = mutableListOf<Pair<Int, Int>>()

    (0 until n).forEach { _ -> meetings.add(nextInt() to nextInt()) }

    meetings.sortBy { it.first }
    meetings.sortBy { it.second }

    var m = 0
    var res = 0

    (0 until n).forEach { i ->
        if (meetings[i].first /* a */ < m) return@forEach

        res++
        m = meetings[i].second /* b */
    }

    println(res)
}

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val n = nextInt()
    val meetings = mutableListOf<Pair<Int, Int>>()

    (0 until n).forEach { _ -> meetings.add(nextInt() to nextInt()) }

    meetings.sortBy { it.first }
    meetings.sortBy { it.second }

    var m = 0
    var res = 0

    (0 until n).forEach { i ->
        if (meetings[i].first /* a */ < m) return@forEach

        res++
        m = meetings[i].second /* b */
    }

    println(res)
}

후기

이 문제의 핵심은 끝나는 시간대로 정렬해 그리디 알고리즘을 적용하는 것이다.

이 문제는 그리디 알고리즘의 대표적인 예시로 알려져 있다. 그리디 알고리즘이 사용 가능한지에 대한 엄밀한 증명은 너무 복잡하므로, 보다 실력을 키우고 다시 도전해볼 수 있으면 좋을 것 같다. 한편, 그리디 알고리즘인지 파악하는 것은 먼저 직관적으로 생각해보는 것이 중요할 것 같다.

@misc{devngho202520250102boj1931,
  author       = {Yu, Dongho},
  title        = {BOJ 1931: 회의실 배정},
  howpublished = {\url{https://ngho.dev/posts/20250102boj1931}},
  year         = {2025},
  month        = {jan},
  note         = {Accessed: 2025-02-05}
}

@misc{devngho202520250102boj1931,
  author       = {Yu, Dongho},
  title        = {BOJ 1931: 회의실 배정},
  howpublished = {\url{https://ngho.dev/posts/20250102boj1931}},
  year         = {2025},
  month        = {jan},
  note         = {Accessed: 2025-02-05}
}