풀다 백준 2568

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

문제를 해결하다

이 문제를 분석해서 좀 더 일반적인 상황으로 바꿔보세요… 마지막으로 A가 정렬되면 연결된 배열 B를 정렬할 때 교차가 발생하지 않는다는 것을 알 수 있습니다.

배열 B를 정렬하려면 최소 요소 수를 제거하여 배열 B를 정렬해야 합니다. 바꾸어 말하면… 배열 B에서 정렬된 최대 길이 요소 집합을 찾아야 합니다. 따라서 이 문제는 LIS(Longest Subsequence) 문제임을 알 수 있습니다.

LIS 문제의 일반 솔루션인 dp에 대한 솔루션의 시간 복잡도는 O(N^2)입니다. N의 한계는 100,000이므로 N^2 알고리즘으로 설계하면 시간 내에 문제를 해결할 수 없습니다. 따라서 적어도 O(NlogN) 시간복잡도로 풀어야 한다.

보면서 문제를 해결하려 했지만… 방법이 생각나지 않았다. logN에서 검색을 수행해야 하기 때문입니다. 이진 검색으로 보였는데 제가 원래 설계한 O(N^2) dp 배열에 이진 검색을 하려고 했더니 방법을 찾을 수가 없었습니다.

그래서 구글링을 해서 O(NlogN) LIS 솔루션을 찾았습니다.

https://4legs-study.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";
    }
}

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