BOJ 백준 1374번 강의실

 

BOJ 백준 1374 강의실

 

문제: https://www.acmicpc.net/problem/1374

1374번: 강의실

 

 

한 강의실에서는 둘 이상의 강의를 동시에 진행하지 못하고 오직 하나의 강의만 진행 가능할 때, N개의 모든 강의를 끝내는 데 필요한 최소 강의실 수를 구해야 한다.

 

처음 문제를 보고 탐욕 알고리즘(Greedy Algorithm)으로 해결하는 문제임을 눈치챘다. 난이도가 크게 어렵지 않으면서 주어진 데이터를 정렬하여 풀어야 하는 탐욕 알고리즘 문제의 경우 정렬 기준을 잘 정하는 것이 관건인 것 같다. 어디까지나 정석이 아닌 스킬이긴 하지만 말이다.

 

 

정렬하여 풀어야 하는 Greedy Algorithm 문제 해결의 핵심 key

 

1. 한 가지 이상의 정렬 기준을 통해 우선 순위를 적절히 설정하여 정렬하기

2. 주어진 데이터를 조합한 새 데이터를 가지고 정렬하기

 

이 문제 해결에 있어서는 1번 방법을 택하는 것이 합리적이라고 보았다. N개의 모든 강의를 진행해야 하므로 우선 빨리 시작해야 하는 강의부터 강의실을 배정해야 한다. 그러므로 N개의 강의를 시작 시간이 이른 순으로 정렬하는데, 시작 시간이 서로 같은 강의는 끝나는 시간이 이른 순으로 정렬한다. 

 

 

이후 앞에서 정렬한 순서대로 강의를 하나씩 강의실에 배정할 것이다. 현재 보고 있는 강의, 즉 시작해야 하는 강의를 강의 A라고 하자. 그리고 이제까지 시작했다고 알고 있는 강의 중에서 가장 일찍 끝나는 강의를 강의 B라고 하자. 

 

 

 

1) 강의 A가 시작하는 시간이 강의 B가 끝나는 시간보다 이르면 강의 B가 진행되는 강의실에는 강의 A를 배정하지 못한다. 그러면 다른 강의가 진행되고 있는 나머지 강의실에는 강의 A를 배정할 수 있을까? 그렇지 않다. 강의 B가 이제까지 진행되고 있는 강의 중에서 가장 일찍 끝난다고 전제하였는데, 이보다 더 늦게 끝나는 강의실에 배정하면 두 개 이상의 강의가 한 강의실에서 같이 진행되므로 문제 조건에 위반된다.

 

2) 강의 A가 시작하는 시간이 강의 B가 끝나는 시간과 같거나 늦으면 강의 B가 진행되었던 강의실에 강의 A를 배정할 수 있다. 다른 강의실에 배정하는 것도 진행 중인 강의가 없으면 가능은 하겠지만, 최대한 강의 시간 사이의 공백을 줄여서 뒤로 갈수록 강의실을 추가로 필요로 하는 가능성을 줄여야 하므로 강의 B가 진행된 강의실에 배정하는 것이 바람직하다.

 

 

C++에서는 자료구조 pair를 이용하거나 프로그래머가 정의한 구조체의 연산자 우선 순위 정의, 정렬 함수 정의 등 방법으로 해결할 수 있을 것이다.

 

이와 비슷한 유형의 문제 중에서는 강의실 수가 주어지고 그 강의실에 배정할 수 있는 최대 강의 수를 구해야 하는 것도 존재한다.

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using lecture = pair<int, int>;

// 강의가 끝나는 시간을 기준으로 정렬해야 하므로 (끝나는 시간, 시작 시간)
priority_queue<lecture, vector<lecture>, greater<lecture>> pq;

int main(){
    int n; scanf("%d", &n);
    vector<lecture> lectures(n);
    
    for (int i = 0; i < n; i++){
        int index, start_time, end_time;
        scanf("%d %d %d", &index, &start_time, &end_time);
        lectures[i].first = start_time;
        lectures[i].second = end_time;
        // 강의 시작하는 시간을 기준으로 정렬해야 하므로 (시작 시간, 끝나는 시간)
    }
    
    sort(lectures.begin(), lectures.end());
    
    int room_num = 0;
    
    for (int i = 0; i < n; i++){
        if (pq.size() > 0){
            // 이제까지 진행한 강의 중 가장 빨리 끝난 강의보다 더 일찍 시작하는 경우
            if (pq.top().first > lectures[i].first){
                room_num += 1;
            }
            // 이제까지 진행한 강의가 끝난 후 현재 강의를 실행할 수 있는 경우 끝난 강의를 빼야 하므로
            else {
                pq.pop();
            }
        }
        else{
            room_num += 1;
        }
        lecture add_lecture;
        add_lecture.first = lectures[i].second;
        add_lecture.second = lectures[i].first;
        pq.push(add_lecture);
    }
    
    printf("%d\n", room_num);
    
    return 0;
}