: pq 사용했더니 3퍼센트에서 틀림
들어오는 시간을 기준으로 하기에는 int,out 시간이 길수록 ,
최대 들어오는 회의실 수가 작아지므로, 옳지 못함.
그림을 그렸을 때 , 나오는시간을 기준으로 해서 만들수 있지 않을까? 란
생각을 했음.
그러면서 , 나오는 시간과 들어가는 시간 간격을 기준으로 접근하면 되지 않을까? 라는 생각을 했고, 밑의 그림을 그림.
1) 정렬 후에 0번째 인덱스를 집어넣고, second가 다음 second보다 크거나
동일하면 무조건 집어넣음.
2 - 1) 그렇게 해서 12 8 이 들어감. 11과 8을 비교해야 하는데
이렇게 생각할 수 있음. 동일한 second에서는
diff가 더 작은 것이 들어와야 회의실에 들어가는
빈도수가 더 높아짐. 일단 이렇게 만 생각을 함.
2 - 2) 이후에 다 패스된 후, 8과 3이 들어감. 이렇게 될 경우
여기서 총 3회로 끝나버림. 뒤에 오는 인덱스의 원소들은 들어 갈 수 없음.
2 - 3) 힌트를 보면 5,7 // 1,4 가 들어감.
2 - 4) 8 , 3이 들어간 상황에서, second값 3보다 다음 second값이 더 크다고 한다면???? 한 원소에서의 diff 차이가 더 작아지게 되고, 이렇게 되면,
빈도수가 더 많아지지 않을까란 생각을 하게 됨.
--> 이유 : second값은 항상 first값보다 작은 상황임.
그런데 현 원소의 second보다 다음 second가 더 크다라는 의미는
diff차이가 반드시 작을수 밖에 없다라는 의미임.
: 반례를 생각할 수 없다면, 시퀀스를 바꿔보는 것도 나쁘지 않음!
second값을 가장 낮게 설정하는 방식으로 바꾸고 싶으므로.
second를 그냥 sort의 대상이 되도록 벡터의 first값으로
변경해서 시도하도록 하자.
sort는 first를 디폴트로 해서 변경하므로.
반례
3
1 3
3 4
4 4
https://www.acmicpc.net/board/view/93999
: 반례에 대해서 생각할 수 없으니 시퀀스를
바꾸는 시도를 해보는게 더 빠를 수 있음.
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>
#include <queue>
bool compare(pair<int, int>a, pair<int, int>b)
{
// 만약세 second 값이 동일할 경우는 어떻게 할것인가.
if (a.second == b.second)
{
// first값이 큰 값이 우선순위가 되도록 하자.
return a.first < b.first;
}
return a.second < b.second;
}
int main()
{
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// 1 4
// 3 5
// 0 6
// 5 7
// 3 8
// 5 9
// 6 10
// 8 11
// 8 12
// 2 13
// 12 14
// pair 값으로 입력을 한 다음에
// 동일한 sort 한 다음에
// 동일한 first에서 가장 작은 second값일 경우에.
// 넣어둠.
int n;
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 from = v[0].first;
int to = v[0].second;
int ret = 1;
for (int i = 1; i < n; ++i)
{
if (to > v[i].first)
continue;
from = v[i].first;
to = v[i].second;
++ret;
// 88퍼센트에서 틀려서 다른 로직으로 만들어보자.
//if (to <= v[i].에first)
//{
// from = v[i].first;
// to = v[i].second;
// ++ret;
//}
//cout << v[i].first << ' ' << v[i].second << endl;
}
cout << ret;
// 0 6부터 들어오게 되면, 답이 3 밖에 안됨.
// 시작값이 1,4가 들어오게 해야 함.
// 생각 회의실에 입장하는 순서가 중요한 게 아니라.
// 나가는 순서가 가장 낮은순으로 정렬을 한다면.
// 알아서 최대 빈도수를 구할 수 있을 듯 함.
}
코드를 입력하세요
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>
#include <queue>
bool compare(pair<int, int>a, pair<int, int>b)
{
return a.second < b.second;
}
int main()
{
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// 1 4
// 3 5
// 0 6
// 5 7
// 3 8
// 5 9
// 6 10
// 8 11
// 8 12
// 2 13
// 12 14
// pair 값으로 입력을 한 다음에
// 동일한 sort 한 다음에
// 동일한 first에서 가장 작은 second값일 경우에.
// 넣어둠.
int n;
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 from = v[0].first;
int to = v[0].second;
int ret = 1;
for (int i = 1; i < n; ++i)
{
if (to <= v[i].first)
{
from = v[i].first;
to = v[i].second;
++ret;
}
//cout << v[i].first << ' ' << v[i].second << endl;
}
cout << ret;
// 0 6부터 들어오게 되면, 답이 3 밖에 안됨.
// 시작값이 1,4가 들어오게 해야 함.
// 생각 회의실에 입장하는 순서가 중요한 게 아니라.
// 나가는 순서가 가장 낮은순으로 정렬을 한다면.
// 알아서 최대 빈도수를 구할 수 있을 듯 함.
}
회의실에서 퇴장하는 시간이 작아야 한다는 것에 초점을 두어야 함.
왜냐하면 일정한 시간에 많은 회의실을 사용해야 하므로.
퇴장 시간이 낮을수록 더 많은 회의실 사용이 가능함.
그래서 퇴장시간을 기준으로 해서 정렬을 함!그리고 입장시간을 기준으로 해서 다음에 들어올 시간을 정함.
첫번째 코드 풀이
#include <iostream> #include <vector> using namespace std; #include<algorithm>
int main()
{
// 일단 정렬을 한 다음에...
// 맨 앞에 있는것부터 마지막 까지 돌리면서
int n;
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());
int start = 0;
int end = 0;
for (int i = 0; i < n; ++i)
{
// 맨앞에서부터 뒤에 까지 시작하는 반복문.
start = v[i].first;
end = v[i].second;
for (int j = i + 1; j < n; ++j)
{
int nStart = v[j].first;
int nEnd = v[j].second;
}
}
}
-> from의 값으로 정렬 한다음에, 이중포문 식으로 돌리려고 했는데,
이렇게 하면 , 효율성이 좋지 못하다라는 것을 생각함.
: 큰돌님이 효율성, 시간복잡도가 높다고 생각하면, 다른 방법으로 시도해보라고 하심...
## 많이 생각해야함.
![](https://velog.velcdn.com/images/kwt0124/post/8bd27029-15e3-4336-a69c-cfbf196cb016/image.png)
-> 위 상태로 진행하면,
1 , 4 -> 5 , 7 // 5 , 9 -> 경우의 수가 2개로 갈라짐.. 이부분을 처리하려면 또 복잡해짐.
-> 어떻게 하면 간단히 처리할 수 있을까를 생각해야함...
## 힌트를 활용하자.
![](https://velog.velcdn.com/images/kwt0124/post/2711f7c5-8db1-46a7-82e7-fd9b785c4d3a/image.png)
![](https://velog.velcdn.com/images/kwt0124/post/3f07f491-4cb7-4405-be4f-780c5f320e47/image.png)
: from ~ to 에서 to 시간대로 정렬을 한다음에 처리를 하고 있는데,,,
어렵다..