[백준 2586] 전깃줄 - 2 (C++)

문제 링크: www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

1. 주의할 점

- 일반적으로 알고 있는 LIS의 공식은 길이를 구하는 것으로, 실제 LIS를 구하는 것은 추가 작업이 필요하다

 

2. 구현

- 모든 수를 Info 구조체 형태의 Vector로 입력 받고, 첫 번째 인자를 기준으로 오름차순 정렬한다

- DP[] 배열을 통해 LIS의 간략한 형태를 구하고, Pos[] 배열을 통해 추가 또는 수정된 원소가 몇 번째 DP 원소와 바뀌었는지 저장한다

- 기존 LIS의 길이를 구하는 것과 같은 방식으로 추가 또는 이분탐색을 통해 교환 위치를 찾으며, Pos[] 배열을 통해 현재 원소가 DP[]의 어떤 위치의 원소와 교환되었는지 체크한다

- Pos[] 배열의 역순으로 탐색하며, LIS의 길이 Cnt+1에서 1을 빼고 시작한다(배열의 인덱스가 0부터 시작이므로)

- 현재 Pos[] 배열의 값이 Cnt와 같다면 해당 원소가 실제 LIS의 부분이므로, 같지 않은 경우 Temp 벡터에 추가한다(삭제할 전깃줄이므로)

- 모든 탐색이 끝난 후, Temp 벡터에는 값이 역순으로 입력되었으므로 뒤에서부터 출력한다

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[500001];
int pos[500001];
struct info{
    int idx,val;
};
bool cmp(info &a, info &b){
    return a.idx < b.idx;
};
info tmp;

int b_search(int r, int v){
    int l=0,mid,result=r;
    while(l<=r){
        mid = l + (r-l)/2;
        if(dp[mid]>=v){
            result = mid;
            r = mid-1;
        }
        else
            l = mid+1;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,a,b,idx=0;
    vector<info> v;
    cin>>num;
    for(int i=0;i<num;i++){
        cin>>a>>b;
        tmp.idx = a;
        tmp.val = b;
        v.push_back(tmp);
    }
    sort(v.begin(),v.end(),cmp);
    
    dp[0]=v[0].val;
    pos[0]=0;
    for(int i=1;i<v.size();i++){
        if(v[i].val > dp[idx]){
            dp[++idx] = v[i].val;
            pos[i]=idx;
        }
        else{
            int vv = b_search(idx,v[i].val);
            dp[vv] = v[i].val;
            pos[i]=vv;
        }
    }    
    cout << v.size()-(idx+1)<<'\n';
    int cnt = idx;
    vector<int> temp;
    for(int i=v.size()-1;i>=0;i--){
        if(pos[i]==cnt) cnt--;
        else    temp.push_back(v[i].idx);
    }
    for(int i=temp.size()-1;i>=0;i--)
        cout << temp[i]<<'\n';
    return 0;
}