[LIS] BOJ 2568 전깃줄 - 2 (C++)

https://www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

 

문제 해결 알고리즘

 

LIS알고리즘에서 길이와 수열을 구하는 문제이다.

 

좀 달랐다면 여기서는 제거해야할 원소의 갯수와 위치를 출력한다는 점인데,

 

그 부분은 record 배열에서 LIS가 아닌 부분을 출력하면 그만인 문제이다.

 

아래의 링크에 자세한 설명이 있다.

 

https://kimmessi.tistory.com/191

[알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int N;
int arr[500010], LIS[500010], record[500010];
int MAX = 0, MAX_num = 0, start_num = 500010;
stack<int> result;

int binary_search(int left, int right, int target){

    int mid;
 
    while(left < right){
 
        mid = (left + right) / 2;
 
        if(LIS[mid] < target) left = mid + 1;
        else right = mid;
 
    }
 
    return right;

}

int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> N;

    for(int i=0;i<N;i++){
        int idx, num;
        cin >> idx >> num;

        MAX_num = max(MAX_num, idx);
        start_num = min(start_num, idx);

        arr[idx] = num;
    }

    int j = 1, i = start_num+1;
    LIS[1] = arr[start_num];
    record[start_num] = 1;

    while(i <= MAX_num){

        if(LIS[j] < arr[i]){
            LIS[++j] = arr[i];
            record[i] = j;
        }
        else{
            if(arr[i] == 0)  record[i] = 0;
            else{
                int idx = binary_search(1, j, arr[i]);
                LIS[idx] = arr[i];

                record[i] = idx;
            }
        }

        MAX = max(MAX, record[i]);
        i++;
    }


    for(int i=MAX_num;i>0;i--){
        if(record[i] == 0) continue;

        if(MAX == record[i]) MAX--;
        else result.push(i);
    }

    cout << result.size() << '\n';

    while(!result.empty()) {
        cout << result.top() << '\n';
        result.pop();
    }

}