BOJ 1931

그리디 알고리즘 문제는 언제나 어렵다... 아직 충분히 익숙하지 않기 때문이리라.

BOJ 1931은 전형적인 그리디 알고리즘 문제라고 한다. 원래는 dp를 사용해서 이 문제를 풀려고 했으나, 시간복잡도가 $O(n^2)$에서 더 이상 낮아지지 않았다. 따라서 결국은 인터넷의 도움을 받았다.

아래는 내가 원래 하려고 했는 방식의 풀이이다.

from sys import stdin

input = stdin.readline


def main():
    count = int(input())

    councils = list()
    for _ in range(count):
        councils.append([tuple(map(int, input().split())), 0])
    councils.sort(key=lambda x: x[0])

    total_max = 0
    for i in range(count-1, -1, -1):
        council = councils[i][0]
        possible_max = 1
        for j in range(i+1, count):
            other, possible = councils[j]
            if council[1] <= other[0]:
                possible_max = max(possible_max, 1 + possible)
        councils[i][1] = possible_max
        total_max = max(total_max, possible_max)

    print(total_max)


if __name__ == '__main__':
    main()

이 문제에서 중요한 것은 결국 정해진 시간 안에 얼마나 많은 회의들을 욱여넣을 수 있느냐이기 때문에, 회의를 시작하더라도 그 다음에 넣을 수 있는 회의의 개수가 최대가 되는 선택들을 어떻게 할 수 있느냐가 중요한 논지이다. 이 문제에서는 회의들을 끝나는 시간으로 정렬하여, 가능한 회의 중에서 끝나는 시간이 가장 빠른 회의들을 모두 선택했을 때에 몇개까지 회의를 진행할 수 있는지에 대해서 계산하는 것이 논지였다.

그리디 알고리즘은 언제나 최적의 답을 주지는 않는다. 나는 언제나 최적의 답을 구하는 것이 지속가능하다고 생각하는 반면, 그리디 알고리즘은 "일단 답이 나오면 됐다"같은 식이라 나와는 성격이 잘 맞지 않는 것 같다.

어쨌든 문제를 잘 풀 수 있었고, 인터넷에서 힌트를 받았기 때문에 죄책감에 공부 노트를 작성한다. 아래는 내가 작성한 코드이다.

def main():
    count = int(input())

    councils = list()
    for _ in range(count):
        councils.append(tuple(map(int, input().split())))
    councils.sort(key=lambda x: (x[1], x[0]))

    end_time = 0
    count = 0
    for council in councils:
        if council[0] >= end_time:
            count += 1
            end_time = council[1]

    print(count)


if __name__ == '__main__':
    main()

이 코드를 사용하면 결국 회의의 개수를 얻어내는 데에는 $O(n)$ 시간밖에 걸리지 않기 때문에, 정렬에 필요한 시간 $O(n \log n)$이면 작업을 완료할 수 있다는 것이 된다.

Ps

글을 쓰고 나서 읽어보니 위에서 dp를 이용해 풀려고 했더 풀이의 방법 자체는 아래에 있는 코드와 비슷하다는 생각이 들었다. 하지만 위에서는 그러한 풀이의 개수를 가진 경우를 모두 알아보기 위해서 모든 경우를 다 둘러보았고, 아래에서는 그 중에 하나만 둘러보았다.

또한 위에 있는 풀이는 아래에서 한 것과 같은 방식을 거꾸로, 시작 시간을 정렬하여 가장 시간이 느린 것부터 몇 개까지 회의가 가능한지 알아보는 방식으로 진행했다.

나는 생각보다 정답에 가까웠던 것이다.

풀이에 참고한 글

• choco1drink (2022), "[BOJ] 1931 - 회의실 배정"