백준 2568번 풀이

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

2568번: 전깃줄 - 2

문제 풀이

이 문제를 분석하여 좀 더 일반적인 상황으로 바꿔보면.. 결국 A가 정렬되어 있을때, 연결된 B 배열이 정렬되어 있어야 교차가 일어나지 않는 것을 알 수 있다. 

B 배열을 정렬하기 위해 최소한의 원소를 제거하여 B배열을 정렬해야한다. 말을 바꿔서 해보면... B배열에서 최대 길이의 정렬된 원소집합을 찾아야한다. 따라서... 이 문제는 LIS(최장 부분 수열)문제라는 것을 알 수 있다.

LIS문제의 일반적인 해결책인 dp를 통한 해결은 시간 복잡도가 O(N^2)이다. N의 제한은 100,000이므로 N^2알고리즘으로 설계하면 시간내에 문제를 해결할 수 없다. 따라서 최소한 O(NlogN) 시간복잡도로 해결해야한다.

문제를 요리조리 보며 해결하려고 했지만.... 도저히 방법이 떠오르지 않았다. 탐색을 logN 에 해야하기때문에.. 이진 탐색인거 같긴했으나 내가 원래 설계한 O(N^2) dp배열에서 이진탐색을 수행하려고 하니 도저히 방법이 떠오르지 않았다.

그래서 구글링하여 O(NlogN) LIS해결법을 찾았다.

https://4legs-study.tistory.com/106 (감사합니다.)

이 해결법을 보고 배운점은 dp 방식을 바꿀 수도 있다는 것이다. 혼자 힘으로 이진탐색을 써야한다는 것까지 유추했으나.. 더 이상 방법을 떠올리지 못했다. 이진탐색이 가능하게 하기 위하여 dp배열을 정렬된 형태로 변형하여 새롭게 점화식 규칙을 만드는 시도를 했어야하는데.. 그렇게 할 생각을 아예 못했다. 발상이 떠올랐다면 최대한 그 쪽으로 구현하려고 설계해보자.

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

typedef struct line
{
    int a,b;
}   line;

bool operator<(const line &l1, const line &l2)
{
    return l1.a < l2.a;
}

int dp[100001];
int idx[100001];

int rec[100001];
line ln[100000];
int islis[500001];

int main()
{
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int N;
    cin >> N;
    for (int i = 0 ; i < N ; ++i)
        cin >> ln[i].a >> ln[i].b;
    
    sort(ln, ln + N);

    int max_len = 0;
    vector<int> del;
    for (int i = 0 ; i < N ; ++i)
    {
        int k = lower_bound(dp, dp + max_len + 1, ln[i].b) - dp; 
        if (k > max_len)
        {
            idx[k] = i;
            dp[k] = ln[i].b;
            rec[i] = k;
            ++max_len;
        }
        else
        {
            idx[k] = i;
            dp[k] = ln[i].b;
            rec[i] = k;
        }
    } 
    cout << N - max_len << "\n";

    int cur = rec[idx[max_len]];
    islis[idx[max_len]] = 1;
    for (int i = idx[max_len] ; i >= 0 ; --i)
    {
        if (cur - 1 == rec[i])
        {
            cur = rec[i];
            islis[i] = 1;
        }
    }

    for (int i = 0 ; i < N ; ++i)
    {
        if (!islis[i])
            cout << ln[i].a << "\n";
    }
}

메모리: 5928 KB, 시간: 36 ms