취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2568번 문제인 전깃줄 - 2이다.
문제는 아래 링크를 확인하자.

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

최소한의 전깃줄을 지워 전깃줄이 교차하는 부분을 없앤다는 것은 최대한의 교차하지 않는 전깃줄을 남긴다는 말과 같다. 최대한의 교차하지 않는 전깃줄의 개수는 LIS를 구하는 것과 같다는 것을 알 수 있을 것이다.

따라서, LIS의 크기를 구하고 LIS를 역추적하여 아무거나 하나를 구한 다음 그 전선들을 제외한 나머지 전선들을 없애는 것으로 문제를 해결할 수 있다.

(세그먼트트리로 LIS 구하기 연습1)

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int parent[500001];
vector<pair<int,int>> arr;
int seg[1048577];

int update(int L, int R, int qI, int qVal, int sI) {
    if (R < qI || qI < L) return seg[sI];
    if (L == R) return seg[sI] = qVal;
    return seg[sI] = max(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}

int nth(int L, int R, int N) {
    int sI = 1;
    while (L < R) {
        if (seg[sI * 2] < N) {
            sI = sI * 2 + 1;
            L = (L + R) / 2 + 1;
        }
        else {
            sI = sI * 2;
            R = (L + R) / 2;
        }
    }
    return L;
}

int rangemax(int L, int R, int qL, int qR, int sI) {
    if (qR < L || R < qL) return 0;
    if (qL <= L && R <= qR) return seg[sI];
    return max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

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

    int N; cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y; cin >> x >> y;
        arr.push_back({ x,y });
    }

    sort(arr.begin(), arr.end());

    int ans = 0;
    int last;
    for (auto node : arr) {
        int x = node.second;
        int temp = rangemax(1, 500000, 1, x, 1);
        parent[x] = nth(1, 500000, temp);
        temp++;
        if (temp > ans) {
            last = x;
            ans = temp;
        }
        update(1, 500000, x, temp, 1);
    }

    for (int i = 0; i < ans; i++) {
        int l = parent[last];
        parent[last] = 9999999;
        last = l;
    }

    cout << N - ans << '\n';
    for (int i = 0; i < N; i++) {
        if (parent[arr[i].second] < 999999) cout << arr[i].first << '\n';
    }
}