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

문제 링크

11000번: 강의실 배정

 

---

풀이 과정

먼저 시간복잡도를 확인해보았다.

시간 제한이 1초, N의 최댓값이 200,000 → N^2 = 40억 (대략 40초) 이기 때문에, 한 강의 시간을 살펴볼 때마다, 다른 강의 시간을 모두 탐색하는(브루트포스) 방법은 적절치 않을 것이라는 전제하에 코드를 작성하였다.

그리고 각 강의실에서 진행되는 모든 강의들 중, 가장 일찍 끝나는 시간을 알아내기 위해서 각 강의실에서 강의가 끝나는 시간의 정렬이 필요했다. 이 경우에는 시간이 새로 입력될 때마다 곧바로 정렬이 이뤄져야했기 때문에 최소 힙을 사용하였다.

for (int i = 0; i < n; ++i) {
    cin >> start >> end;
    // 현재 강의 시간을 배정하는 코드
}

원래는 위처럼 입력을 받으면서 그때그때 강의시간을 배정하려고 하였으나, 여러가지 문제점이 보여서 다른 방법을 모색하게 되었다.

 

⚠️ 위 방법의 문제점

일단, 이 문제를 처음 읽었을 때는 강의 시작 시간이 오름차순으로 주어지는 줄 알고, 아래와 같이 제출했다가 4퍼센트까지 채점되고 틀리는 것을 확인할 수 있었다.

[ 입력 예시 ]
1 3
2 4
3 5

#include <iostream>
#include <queue>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;

    int start, end, cnt = 0;
	// 최소 힙 - logN의 시간복잡도를 가지고 있기 때문에, 이 문제에서 NlogN의 경우(= 단일 for문) 시간초과가 발생하지 않는다.
    priority_queue<int, vector<int>, greater<int>> min_end; // 가장 빠른 강의 종료 시간을 뽑아내기 위한 힙

    cin >> start >> end;
    min_end.push(end);
    cnt++;

    for (int i = 1; i < n; ++i) {
        cin >> start >> end;
        // 현재 보고있는 강의 시작 시간(start)이, "현재까지 입력받은" 가장 빠른 강의 종료 시간보다 이르다면,
        if (start < min_end.top()) {
        // 강의실을 하나 더 배정한다.
            cnt++;
        } else { // 현재 보고 있는 강의 시작 시간이, "현재까지 입력받은" 가장 빠른 강의 종료 시간보다 늦다면,
        // 해당 강의실에 현재 보고있는 강의를 배정한다.
            min_end.pop();
        }
        min_end.push(end);
    }

    cout << cnt << '\n';
}

틀리고 나서 문제를 다시 읽어보니, 강의 시작 시간이 오름차순으로 주어진다는 조건이 없다는 것을 알았다. 따라서, 시간이 뒤죽박죽 주어졌을 때도 통과할 수 있도록 코드를 짜야한다.

위 예시는 통과할 수 있지만, 만약 시작 시간이 아래와 같이 오름차순으로 주어지지 않는 경우에는 정답을 도출할 수 없게 된다.

강의 시간이 연속되지 않은 경우에는, 앞 강의 종료 시간과 뒷 강의 시작 시간 간에 발생한 텀을 무시하기 때문이다.

1 3
5 8
3 4
3 8

위 입력을 예시로 들면,

• 1 → 3 (min_end : 3)
• 1 → 3, 5 → 8 (min_end : 8) ⚠️ 실제 3시와 5시 사이에 텀이 있지만, 이를 8로 덮어 씌워버림
• 1 → 3, 5 → 8 | 3 → 4 (min_end : 4, 8) ⚠️ 1 강의실에 배정받을 수 있음에도 불구하고, 새로운 강의실을 추가
• 1 → 3, 5 → 8 | 3 → 4 | 3 → 8 (min_end : 4, 8, 8)

---

코드 수정

따라서 강의 시간을 모두 입력받고, 이를 오름차순으로 먼저 정렬하였다. 그리고 정렬된 상태에서 순서대로 강의실을 배정하도록 코드를 수정하였다.

→ 강의 시작 시간이 빠른 순, 그리고 강의 진행 시간이 짧은 순(= 강의 종료 시간이 빠른 순)으로 정렬하였다.

결론: 아래 전제가 최적의 결과(최소 강의실 수)를 도출할 수 있다(-> greedy 성립 조건)고 생각하고 코드를 작성하였다.

• 일찍 시작하는 강의부터 차례대로 강의실을 배정한다.
• 앞서 진행된 강의가 최대한 빨리 끝나는 시간을 기준으로, 강의 배정 가능 여부를 판단하고 강의 시간을 배정한다.

결과

#include <iostream>
#include <queue>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    int start, end, cnt = 0;
    // 강의 시간 목록 (최소힙 - 오름차순)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> lectures;
    // 각 강의실의 강의 종료 시간 (최소힙)
    priority_queue<int, vector<int>, greater<int>> end_times;
    
    // 강의 시간을 오름차순으로 정렬한다. push와 동시에 정렬이 이루어짐 (logN)
    for (int i = 0; i < n; ++i) {
        cin >> start >> end;
        lectures.push({start, end});
    }
		
    // 첫 번째 강의실 강의 종료 시간을 end_times에 push
    end_times.push(lectures.top().second);
    // 목록에서 첫 번째 강의 시간을 pop
    lectures.pop();
    // 강의실 수를 1 증가
    cnt++;
	
    // 시간 복잡도 - NlogN (20만 * 약 17 = 약 340만)
    for (int i = 1; i < n; ++i) {
        start = lectures.top().first;
        end = lectures.top().second;
        
        // 현재 강의 시작 시간이, 앞선 강의들 중 가장 빠른 종료 시간 이후라면,
        if (start >= end_times.top()) {
        	// 해당 강의의 바로 뒤에 강의를 배정한다.
            // -> 앞 강의 종료 시간을 무효시킨다.
            end_times.pop();
        } else { // 시간이 겹친다면,
        	// 강의실을 추가한다.
            cnt++;
        }
        // 현재 강의 종료시간을 힙에 추가한다.
        end_times.push(end);
        // 다음 강의 시간을 보기 위해, 현재 강의 시간을 pop
        lectures.pop();
    }

    cout << cnt << '\n';
}

---

그리디 알고리즘

이번 문제에서 사용된 개념은 그리디 알고리즘이다. 

그리디 알고리즘은 매 순간 가장 최선의 선택을 하는 방법으로, 여기서 중요한 것은 해당 선택이 최선의 결과를 도출할 수 있는지 입증되어야 한다.

그리디 알고리즘의 핵심은 순간의 가장 좋은 선택이 문제 해결 방법이 될 수 있는지 입증하는 것이다. 그리디 알고리즘에서는 전제를 올바르게 설정하고 코드 구현에 돌입하는 것이 좋다. 

 

해당 내용을 숙지하고, 이번 문제 풀이에서는 올바른 전제를 설정하는 것에 초점을 두고 코드를 작성하였다.