[BOJ 2568] 전깃줄 - 2

문제 출처 : https://www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 유형의 문제이다. 

전깃줄이 순서없이 입력되기 때문에 A 또는 B를 기준으로 정렬을 해주어야 한다. 

A를 기준으로 정렬한다면, 정렬된 후의 B 수열을 가지고 LIS 알고리즘을 이용한다. 

 

LIS 알고리즘 (https://wogud6792.tistory.com/33)

LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열

 

 

이 때, 출력하고자 하는 것이 LIS의 길이뿐만 아니라 구체적인 LIS도 알아야 하고,

A에 연결된 번호를 출력해야 하므로 B를 기준으로 정렬했다면 없어진 전깃줄을 찾아 A와 연결해야 한다. 

(B를 기준으로 정렬했다면 더 간단했을거 같기도 하다...)

 

소스 코드)

//BOJ 2568 전깃줄 - 2
#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<functional>
#include<string>
 
using namespace std;
 
struct line {
    int A;
    int B;
};
bool compare(line a, line b) {
    return a.A < b.A;
}
 
line L[100001];
int A[500001];
int ans[100001];
int index[100001];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N; 
    int idx = 0;
    int a, b;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> a >> b;
        L[i].A = a;
        L[i].B = b;
    }
    sort(L+1, L + N+1, compare);
 
    for (int i = 1; i <= N; i++) {
        if (idx == 0)
        {
            A[idx++] = L[i].B;
            index[1] = 1;
        }
        else {
            if (A[idx - 1] < L[i].B)
            {
                index[i] = idx+1;
                A[idx++] = L[i].B;
            }
            else {
                index[i] = lower_bound(A, A + idx, L[i].B) - A+1;
                A[lower_bound(A, A + idx, L[i].B) - A] = L[i].B;
            }
        }
    }
 
    cout << N-idx << '\n';
    int t = 0;
 
    for (int i = N; i >= 1; i--) {
        if (idx == index[i]) idx--;
        else {
            ans[t++] = L[i].A;
        }
    }
    sort(ans, ans + t);
    for (int i = 0; i < t; i++) cout << ans[i] << '\n';
}