BOJ 7888 - Two professors

체감 난이도: D5

태그: 그리디, 정렬, 우선순위 큐

문제 요약: 최소 개수의 강의실을 사용해 모든 강의를 진행하게 한다.

(단 1번 강의와 2번 강의는 같은 강의실에 배정하면 안 된다.)

 

강의실 배정의 상위 버전 문제이다.

 

우선 평범하게 강의실 배정을 하는 로직을 기반으로 생각 해보자.

만약 가장 빨리 끝나는 강의실에 1번 또는 2번 강의가 있는데 2번 또는 1번 강의가 들어온다면 다음으로 빨리 끝나는 강의실에 배정하는 식으로 진행시켜보자.

 

아래와 같은 상황이 들어오면 어떨까?

7
1 2
6 8
1 2
2 4
3 5
4 6
5 7

강의실 배정을 조금 변형한 방법으로는 이 상황을 해결할 수 없다.

 

위 상황을 조금 보기 쉽게 정렬해보면 아래와 같다.

1 2 (1)
1 2 (3)
2 4 (4)
3 5 (5)
4 6 (6)
5 7 (7)
6 8 (2)

()안에 있는 수는 처음 들어온 순서이다.

처음 고안한 방법은 1번과 2번이 양 끝에 들어오게 되면 반례가 생기는 것이다!

 

위 상황에서는 최소 개수의 강의실로 배정하는 방법으로는 (1,5,7),(2,3,4,6)이 있다.

여기서 적절히 관찰을 해준 뒤 발견 할 수 있는 사실 하나를 추가해 주면 문제를 해결할 수 있다.