교차하지 않게 하기 위해서 없애야 하는 전깃줄을 구하는 것은 교차하지 않게 남길 수 있는 전깃줄의 최대 개수를 구하는것과 동일한다. 그리고 이것은 가장 긴 증가하는 부분수열과 같은 문제가 된다.
없애야 하는 전깃줄 번호도 구해야 하기 때문에 이전에 풀었던 가장 긴 증가하는 부분수열 문제를 그냥 그대로 이용하면 된다.
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<pair<int,int>>lines;
vector<int> lis;
vector<int> last;
int ind[100004];
void solve()
{
for(auto i=lines.begin();i<lines.end();i++)
{
if(lis.empty())
{
lis.push_back((*i).second);
ind[i-lines.begin()] = 0;
}
else{
int x = lower_bound(lis.begin(),lis.end(),(*i).second) - lis.begin();
if(x==lis.size())
{
lis.push_back((*i).second);
ind[i-lines.begin()] = lis.size()-1;
}
else{
lis[x]=(*i).second;
ind[i-lines.begin()] = x;
}
}
}
}
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
int a,b;
scanf("%d %d",&a,&b);
lines.push_back(make_pair(a,b));
}
sort(lines.begin(),lines.end());
solve();
int ans = lis.size();
printf("%d\n",N-ans);
ans--;
for(int i=N-1;i>=0;i--)
{
if(ind[i]==ans)
{
//last.push_back(i);
ans--;
}
else
{
last.push_back(lines[i].first);
}
}
for(auto i=last.end()-1;i>=last.begin();i--)
{
printf("%d\n",(*i));
}
}같은 문제라서 vector 공부도 해볼겸 구현을 조금 다른 방식으로 했다.
이분탐색으로 다음 숫자가 들어갈 위치를 찾았던 부분도 lower_bound라는 라이브러리 함수를 이용해서 처리했다.
