[C++] 11000번 강의실 배정 - 문제 해결 Point

1. 문제 해결 Idea

문제를 읽고 처음 생각해낸 Idea는

일찍 끝나는 수업부터, 공백이 최소가 되도록 배치하자! 였다. 

 

이 생각을 바탕으로 머리를 쥐어짜보고, 도저히 안돼서 다른 분들 풀이도 읽어보니

이 문제를 풀기 위한 (그리고 풀이를 이해하기 위한..) 

가장 중요한 Point는 다음과 같다.. ^-ㅠ

 

배치 완료된 수업 목록은 끝나는 시간을 기준으로,
새로 배치할 수업은 시작 시간을 기준으로 생각해야한다.

 

2. 해설

ex) 

입력 :
4
1 3
2 4
4 6
3 11

출력 :
2

배치 완료된 수업 목록은 <오름차순 priority queue> sche 에 넣는다.

그럼 새로 배치할 수업은 sche 의 top인 "가장 일찍 끝난 수업"과만 만나서 합칠 수 있는지 여부를 체크할 것이다.

-> 이때 "가장 일찍 끝난 수업"과도 합칠 수 없다면, 즉 가장 일찍 끝나는 수업보다도 더 일찍 시작하는 수업이었다면

sche 의 그 어떤 수업과도 합칠 수 없다. 더 늦게 끝날 테니까!

 

또한 새로 배치할 수업은 어떤 순서로 들어오느냐..

일찍 시작하는 순서대로 들어와서 체크해야한다.

-> 그래야 앞 타임의 "가장 일찍 끝난 수업"과의 시간 공백이 최소가 될 것이다.

 

합칠 수 있다면 합치고,

-> 새로 배치할 수업을 sche 에 push

-> 합쳤으니 "가장 일찍 끝난 수업"인 sche의 top은 pop

합칠 수 없다면 그냥 새로 추가한다.

-> 새로 배치할 수업을 sche 에 push

 

3. 코드

 

#include <iostream>

#include <queue> //cla, sche

#include <algorithm> //sort

using namespace std;

int main() {

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

/*입력*/

int N;

cin >> N;

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > cla;

for (int i = 0; i < N; i++) {

int s, t;

cin >> s >> t;

 

pair<int, int> p;

p.first = s;

p.second = t;

cla.push(p);

}

//일찍 끝나는 순서대로 정렬

/*계산*/

priority_queue<int, vector<int>, greater<int> > sche; //끝나는 시간 기록

sche.push(cla.top().second);

cla.pop();

while (!cla.empty()) {

if (cla.top().first >= sche.top()) //제일 빨리 끝나는 수업보다 더 빨리 시작하면

sche.pop(); //어떤 수업이랑도 합칠 수 없다는 점을 이용

 

sche.push(cla.top().second);

cla.pop();

}

/*출력*/

cout << sche.size() << "\n";

return 0;

}

 

4. 느낀점

하.. 골드 5인데 왜 이렇게 어려운지 모르겠다

실버와 골드의 차이는 참 크구나...

한참을 고민하다 시간 초과가 계속 나길래

해설을 찾아보는데 해설도 이해하는게 쉽지 않아서

이렇게 한번 정리해봤다.

나같은 누군가가 또 있다면 도움이 됐으면 좋겠다 :)