[백준]전구(2550)

문제 링크 : [백준]전구(2550)

문제 설명

스위치와 매핑되는 전구들의 입력이 주어집니다.
스위치를 눌러 전구를 켜는데, 선이 교차되는 경우에는 켜지지 않습니다.
최대한 많은 전구를 켤 때의 갯수와 그때 눌러야 할 스위치 번호를 구하세요.

입력

N(전구의 갯수, 1 <= N <= 10,000)
S_i(스위치 번호)
L_i(전구 번호)

5
2 4 1 5 3
4 5 1 3 2

출력

3
3 4 5

카테고리

#DP #LIS

시간 복잡도 상한

O(N²)

해결 방법

1. 최대한 교차하지 않는 매핑 갯수를 구해야 합닌다.
2. 스위치 쪽의 값을 무시하고, 인덱스를 값으로 사용하고, 전구와의 매핑관계를 유지한다면, 연결되는 전구가 증가하는 방향으로 연결되어야만 교차하지 않을 수 있습니다.
   2-1. 2, 4, 1, 5, 3을 1, 2, 3, 4, 5로 변경하고,
   2-2. 매핑되는 전구의 번호는 2, 4, 3, 5, 1로 바꿀 수 있습니다.
   2-3. 선을 다시 그려보면 원래 예제와 동일한 그림이 그려지는 것을 확인 할 수 있습니다.
3. 2.에서 변경한 값에서 2, 3, 4를 선택하는 것이 가장 많은 전구를 켤 수 있는 상태이며, 인덱스가 증가하는 값임을 확인 할 수 있습니다.
4. 즉 LIS로 풀 수 있는 문제입니다.
5. 단, 주어진 값으로 풀면 안되고, 2.에서처럼 인덱스로 치환하여 문제를 풀어야 합니다.
6. 눌러야 할 스위치는 lower_bound로 현재 스위치가 들어갈 위치가 파악되면, 벡터에서 그 위치 앞에 있는 스위치 번호를 관리합니다.
7. LIS 벡터가 완성되고, 맨 마지막 요소의 앞에 있던 요소를 찾고, 반복해서 앞에 요소들을 찾아가면서 경로를 찾을 수 있습니다.

시간복잡도

O(N * logN)

코드

#include<cstdio>
#include<vector>
#include<queue>
#define N 10001
using namespace std;
int n,d[N],e[N],f[N],i,x,w;
vector<int>v;
priority_queue<int>q;
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",d+i);
        e[d[i]]=i;
    }
    for(i=1;i<=n;i++){
        scanf("%d",&x);
        w=e[x];
        if(v.empty()||v.back()<w){
            if(v.empty())f[w]=-1;
            else f[w]=v.back();
            v.push_back(w);
        }else{
            x=lower_bound(v.begin(),v.end(),w)-v.begin();
            v[x]=w;
            f[w]=x?v[x-1]:-1;
        }
    }
    x=v.back();
    printf("%d\n",v.size());
    while(x>0){
        q.push(-d[x]);
        x=f[x];
    }
    while(!q.empty())printf("%d ",-q.top()),q.pop();
}