[백준] 전깃줄-2(2568)

문제 링크 : [백준] 전깃줄-2(2568)

문제 설명

두 전봇대 사이에 전깃줄이 연결되어있습니다.
한 전봇대에서 다른 전봇대로 연결된 전깃줄 중 교차되지 않도록 전깃줄을 제거해야합니다.
주어진 전깃줄 연결 중 서로 교차하지 않게 하면서 가장 작은수로 전깃줄을 제거하려면 어떤 전깃줄을 제거해야 하는지 출력하세요.

입력

N(전깃줄 갯수, 1 <= N <= 100,000)
A_i(왼쪽 전봇대의 위치, 1<= A_i <=500,000)
B_i(A_i와 연결되는 오른쪽 전봇대의 위치, 1<=B_i <=500,000)

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

출력

자르는 전깃줄 수와 자르는 전깃줄 위치(오름차순)

3
1
3
4

카테고리

#LIS #DP

시간 복잡도 상한

O(NlogN)

해결 방법

1. 제거를 하는 방법은 너무 많습니다.
2. 반대로 생각해보면, 최소로 제거를 한다는 것은, 최대로 연결된 전깃줄을 확보하는 것과 같습니다.
   2-1. 최대로 연결된 전깃줄을 안다면, 그것에 포함되지 않는 것이 잘린 전깃줄입니다.
3. 전깃줄이 교차하지 않는다는 것은 왼쪽에서의 위치와 오른쪽에서의 위치가 서로 교차되지 않는다는 것입니다.
4. 즉, 왼쪽 전봇대의 위치를 인덱스로 하고 오른쪽 위치를 값으로 하는 배열을 만들어 증가하는 최장 부분수열 LIS를 구하면 되는 문제입니다.
5. 코드를 다시보니 굳이 저렇게 안하고 1차원 배열로 구현을 해도 될 것 같습니다.
6. 단 NlogN LIS를 구할 경우, LIS를 구성하는 원소를 알 수 없어서 다른 장치가 필요합니다.
7. LIS의 동작 원리를 생각해보면, lower_bound를 이용하여 위치를 찾아갈 때, 자신의 앞 위치는 항상 정확하게 찾을 수 있음을 알 수 있습니다.
8. 따라서 lower_bound로 위치를 찾아가면서 앞 요소의 링크들을 저장하는 배열을 만듭니다.
9. LIS 마지막 원소는 항상 가장 긴 원소의 마지막 요소이므로, 역추적하여 LIS 연결 요소들을 찾습니다.
10. LIS 요소에 포함되지 않는 요소들을 출력하여 줍니다.

시간복잡도

O(NlogN)

코드

#include<cstdio>
#include<vector>
#include<algorithm>
#define pi pair<int,int>
#define mp make_pair
using namespace std;
int n,i,j,m;
pi p[100000];
int q[100000];
vector<pi> v;
bool comp(const pi &a,int b){
    return a.first<b;
}
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d %d",&p[i].first,&p[i].second);
    sort(p,p+n);
    for(i=0;i<n;i++){
        if(v.empty()||v.back().first<p[i].second){
            q[i]=v.size()?v[v.size()-1].second:-1;
            v.push_back(mp(p[i].second,i));
            m=i;
        }else{
            j=lower_bound(v.begin(),v.end(),p[i].second,comp)-v.begin();
            q[i]=j?v[j-1].second:-1;
            v[j]=mp(p[i].second,i);
        }
    }
    printf("%d\n",n-v.size());
    while(m>-1){
        p[m].first=-1;
        m=q[m];
    }
    for(i=0;i<n;i++)if(p[i].first>-1)printf("%d\n",p[i].first);
}