[백준 11000 C++] 강의실 배정

오늘은 백준 11000번 강의실 배정 문제에 대해 다뤄볼 예정이다. 

강의실 배정 문제 링크 (백준 11000번 문제): https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

문제 설명

백준 11000번 문제는 S(i)에 시작해서 T(i)에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 예를 들어, 1시 ~ 3시까지 수업으로 인해 강의실을 사용하고 있는데, 2시 ~ 4시 수업이 존재할 경우 새로운 강의실을 마련해야한다. 즉, 2개의 강의실이 필요하게 된다. 이 때, 3시 ~ 5시 수업이 존재할 경우에는 1시 ~ 3시에 사용했던 강의실에서 수업을 진행하면 되므로, 추가적인 강의실이 필요하지 않다. 

 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, T(i) ≤ S(j) 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

 

문제 풀이 

백준 11000번 문제에서 주목해야할 점은 프로그램이 1초 안에 진행되어야 한다는 점이다. 시간 내에 통과하기 위해, 그리디 알고리즘을 사용해야함을 알 수 있을 것이다. 그럼, 위 문제를 해결하기 위해 어떤 방식으로 접근해야할까? 

 

우선, 강의실에 수업이 마치는대로 새로운 수업이 진행될 수 있어야한다. 그렇게 하기 위해서는 첫 번째로, 강의가 끝나는 시간과 강의가 시작되는 시간 간에 비교가 이루어져야 할 것 같다. 두 번째로, 비교를 위해 강의가 시작되는 시간을 기준으로 정렬을 해야할 것 같다. 

 

예를 들어, 아래와 같은 입력이 들어왔다고 해보자. 

6

1 3 

2 5

1 7

7 11

9 13

3 9

 

비교를 하려고 하니, 수업이 시작되는 시간이 정렬이 되어 있지 않아 비교를 하는데 어려움이 있다. 

강의가 시작되는 시간을 기준으로 정렬 해주자. 

 

그럼, 아래와 같이 정렬이 될 것이다. 

1 3

1 7 

2 5

3 9 

7 11

9 13 

 

1~3 (강의실 1), 1~7(강의실 2), 2~5(강의실 3), 3~9(강의실 1), 7~11(강의실 2), 9~13(강의실 1) 

즉, 총 강의실이 3개가 필요하다는 것을 알 수 있다. 

 

수업이 끝나는대로 다른 수업이 진행될 수 있도록 하기 위해서는 우선 순위 큐(priority queue)를 사용하여 수업이 마치는 시간을 저장해주고, 수업이 진행될려고 할 때, 새로운 강의실이 필요한지 아닌지 판단해주면 된다. 만약 수업이 마쳐서, 새로운 수업이 진행될 경우에는 큐에서 pop()을 진행해준다. 

 

이를 코드로 나타내면 아래와 같이 나타낼 수 있다.