BOJ 11000 : 강의실 배정 - C++
강의실 배정
코드
[ 나의 실패 풀이 ]
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <deque>
#include <sstream>
using namespace std;
bool compare(pair<int,int> a, pair<int,int> b)
{
if(a.first == b.first) return a.second < b.second;
return a.first < b.first;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N,ans=1,cnt=1;
cin >> N;
vector<pair<int,int>> v(N);
for(int i=0;i<N;i++)
cin >> v[i].first >> v[i].second;
sort(v.begin(), v.end(), compare);
int time = v[0].second;
for(int i=1;i<N;i++)
{
if(time > v[i].first) {
cnt++;
}else{
ans=max(ans,cnt);
time = v[i].second;
cnt=1;
}
}
if(cnt != 1) ans=max(ans,cnt);
cout << ans;
return 0;
}
- 맞다고 생각했던 로직
1) 강의가 끝나는 시간에 따라 정렬한 후 비교하며 해결
--> 강의가 끝나는 시간으로 정렬할 경우 시작 시간이 누락하는 경우 발생
/* 반례
4
1 2
1 4
2 6
4 5
*/
2) 강의가 시작하는 시간에 따라 정렬한 후 단순 차례 비교만 한 경우
(위 코드)
/* 반례 - 시작 시간이 3보다 작은 값들을 모두 지나쳐서 개수만 세면 해당 강의가
끝나는 시간들이 무시된다
4
1 3
2 6
2 10
4 5
*/
[ 정답 코드 ]
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <deque>
#include <sstream>
#include <queue>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
priority_queue<int,vector<int>,greater<int>> pq;
vector<pair<int,int>> v(N);
for(int i=0;i<N;i++)
cin >> v[i].first >> v[i].second;
sort(v.begin(), v.end());
pq.push(v[0].second);
for(int i=1;i<N;i++)
{
if(pq.top() > v[i].first){
pq.push(v[i].second);
}else{
pq.pop();
pq.push(v[i].second);
}
}
cout << pq.size();
return 0;
}
- key point!
1) 입력을 시작 순서
대로 정렬
2) 단순 비교가 아니라 지속적인 영향을 줄 수 있기에 보관해야함
--> priority_queue
사용
(강의 끝시간과 다음 시작시간을 단순비교만 하고 넘어가는것이 아님)
[ 회의실 배정 vs 강의실 배정 ]
- 회의실 배정은 하나의 회의실에 최대한 많은 강의를 할 수 있도록 하는 것
--> 끝시간으로 배열해서 단순 비교
--> 단순 비교라는 것은 영향을 주지 않고 무시되도 되는것!
- 강의실 배정은 최소한의 강의실 개수를 찾기 위한 것
(겹치는 강의 개수를 세어아햠)
--> 강의 끝난 시간이 영향을 계속 줄 수 있어서 자료구조로 유지해서 비교해야함
Author And Source
이 문제에 관하여(BOJ 11000 : 강의실 배정 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-11000-강의실-배정-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
[ 나의 실패 풀이 ]
#include <string> #include <vector> #include <iostream> #include <cmath> #include <map> #include <algorithm> #include <deque> #include <sstream> using namespace std; bool compare(pair<int,int> a, pair<int,int> b) { if(a.first == b.first) return a.second < b.second; return a.first < b.first; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int N,ans=1,cnt=1; cin >> N; vector<pair<int,int>> v(N); for(int i=0;i<N;i++) cin >> v[i].first >> v[i].second; sort(v.begin(), v.end(), compare); int time = v[0].second; for(int i=1;i<N;i++) { if(time > v[i].first) { cnt++; }else{ ans=max(ans,cnt); time = v[i].second; cnt=1; } } if(cnt != 1) ans=max(ans,cnt); cout << ans; return 0; }
- 맞다고 생각했던 로직
1) 강의가 끝나는 시간에 따라 정렬한 후 비교하며 해결
--> 강의가 끝나는 시간으로 정렬할 경우 시작 시간이 누락하는 경우 발생/* 반례 4 1 2 1 4 2 6 4 5 */
2) 강의가 시작하는 시간에 따라 정렬한 후 단순 차례 비교만 한 경우
(위 코드)/* 반례 - 시작 시간이 3보다 작은 값들을 모두 지나쳐서 개수만 세면 해당 강의가 끝나는 시간들이 무시된다 4 1 3 2 6 2 10 4 5 */
[ 정답 코드 ]
#include <string> #include <vector> #include <iostream> #include <cmath> #include <map> #include <algorithm> #include <deque> #include <sstream> #include <queue> using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; priority_queue<int,vector<int>,greater<int>> pq; vector<pair<int,int>> v(N); for(int i=0;i<N;i++) cin >> v[i].first >> v[i].second; sort(v.begin(), v.end()); pq.push(v[0].second); for(int i=1;i<N;i++) { if(pq.top() > v[i].first){ pq.push(v[i].second); }else{ pq.pop(); pq.push(v[i].second); } } cout << pq.size(); return 0; }
- key point!
1) 입력을시작 순서
대로 정렬
2) 단순 비교가 아니라 지속적인 영향을 줄 수 있기에 보관해야함
-->priority_queue
사용
(강의 끝시간과 다음 시작시간을 단순비교만 하고 넘어가는것이 아님)
[ 회의실 배정 vs 강의실 배정 ]
- 회의실 배정은 하나의 회의실에 최대한 많은 강의를 할 수 있도록 하는 것
--> 끝시간으로 배열해서 단순 비교
--> 단순 비교라는 것은 영향을 주지 않고 무시되도 되는것!- 강의실 배정은 최소한의 강의실 개수를 찾기 위한 것
(겹치는 강의 개수를 세어아햠)
--> 강의 끝난 시간이 영향을 계속 줄 수 있어서 자료구조로 유지해서 비교해야함
Author And Source
이 문제에 관하여(BOJ 11000 : 강의실 배정 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-11000-강의실-배정-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)