반응형
SMALL
백준 2457
-
백준 11000, 2457 문제 풀이 (Feat. 그리디 & 파이썬)알고리즘 2024. 3. 8. 14:37
백준 11000번 강의실 배정 문제 설명 N개의 강의 중 i번째 강의가 si시간에 시작해 ti에 끝이난다. 최소의 강의실을 사용하여 모든 강의를 배정하는 방법을 구하는 문제입니다. 문제 풀이 모든 강의를 배정할 수 있는 최소 강의실 개수를 구하는 문제이므로 언제 강의실의 개수가 늘어나는지를 살펴보면됩니다. i번째 강의를 배정할 때 강의실의 개수가 늘어나는 경우는, 현재까지 생겨난 강의실의 마지막 강의가 끝나는 시간이 i 강의의 시작 시간보다 모두 늦은 경우입니다. 기존 강의실에 배정할 수 있는 경우 새로운 강의 C의 시작시간 S3가 두 강의실의 마지막 강의가 끝나는 시간 T1, T2 중 T1보다 크므로 강의실 1에 강의 A가 끝난 뒤 배정하면 됩니다. 새로운 강의실을 배정해야 하는 경우 새로운 강의 C의..