백준 BOJ 2568 - 전깃줄-2

 

가장 긴 증가하는 부분 수열과 같은 문제이다.

 

 

가장 긴 증가하는 부분 수열을 구할때

d[] 배열로 수열의 크기는 알 수 있지만,

수열의 순서를 보장해주진 않는다.

 

따라서

p[]배열에 따로 d[] 배열에서의 인덱스를 저장해놓는다.

 

그 후 가장 큰 인덱스부터 1까지 부분수열인지 체크를 하면된다.

 

이때 수열을 순서대로 출력해야한다면 stack을 사용하면 되고,

이 문제에서는 해당하지 않는 전깃줄만 자르면 되기 때문에 해시맵에 저장을 하면된다.

 

 

 

#include<iostream>
#include<memory.h>
#include<vector>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
int n, m, k;
 
int a[500001];
int d[100001];
int p[500001];
 
int upperbound(int s, int e, int target){
    int lo = s;
    int hi = e;
    while(lo<hi){
        int mid = (lo+hi)/2;
        if(d[mid]<target){
            lo=mid+1;
        }
        else{
            hi=mid;
        }
    }
    return hi;
}
 
 
int main() {
    memset(a,0,sizeof(a));
    memset(p,0,sizeof(p));
    scanf("%d",&n);
    int mm = 999999;
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        a[x]=y;
        if(x<mm){
            mm=x;
        }
    }
    d[1]=a[mm];
    p[mm]=1;
    int idx=1;
    for(int i=1;i<=500000;i++){
        if(a[i]==0) continue;
        if(d[idx]<a[i]){
            d[++idx] = a[i];
            p[i] = idx;
        }
        else{
            int pos = upperbound(1, idx, a[i]);
            d[pos] = a[i];
            p[i]=pos;
        }
    }
 
 
    printf("%d\n",n-idx);
    
    unordered_map<int, bool> mp;
    for(int i=500000;i>=1;i--){
        if(p[i]==idx){
            mp[i]=true;
            idx--;
        }
    }
    
    for(int i=1;i<=500000;i++){
        if(a[i]==0) continue;
        if(mp.count(i)==0) printf("%d\n",i);
    }
 
    
    return 0;
}