[BOJ][1931번] 회의실 배정

안녕하세요 Dibrary입니다.

이번에는 굉장히 유명한 '회의실 배정'문제를 정리해보겠습니다.

사실, 이 문제는 여러 알고리즘 책에 소개가 되었으나 막상 안보고 하려니 잠시 헷갈린 문제입니다.

 

1931번: 회의실 배정

 

---

먼저 예제 입력에 대해서 확인을 해보겠습니다.

총 11개의 가능한 시간이 주어지는데, 이를 엑셀로 표현해보면, 

이렇게 나옵니다. 이 중에 예제 출력의 결과인 4가 나오게 하려면, 

이렇게 골라야 합니다. 

근데, 이때 제가 의문이 들었던 내용은, 첫 번째로 택해진 1, 4에 해당되는 시간 구간은 맨 처음에 시작하는 것도 아니고, 그렇다고 길이가 가장 긴 것도 아니고, 아무것도 아닌데, 그럼 '선택하는 기준'이 뭘까? 였습니다.

 

사실 구간이나 길이, 시작시간 이런건 고려할 대상이 아니었던 것이죠.

가장 빨리 끝나는 것을 기준으로 '정렬' 해 두고, 가장 빨리 끝나는 것을 택한 후에 그다음에 가장 빨리 시작하는 시간을 다시 택해 나가면 됩니다.

이 문제가 왜 그리디에 속하는지 몰랐는데, 이 원리를 알고 나서 부터 '그리디'가 이런 것이구나를 깨닫게 되었죠.

 

코드는 아래와 같습니다.

time.sort 부분에서 끝시간을 기준으로 정렬하는 것을 볼 수 있습니다.

그 뒤에 end_time으로 첫 번째 값을 구한 후에, 그것을 기준으로
for문으로 end_time보다 큰 첫번째 값을 다시 구해 나가고 있습니다.

이렇게 구한 '갯수'가 cnt가 되는 것이죠.