[Baekjoon, 2568] 전깃줄 - 2

두 전봇대 A와 B에서 A를 기준으로 정렬을 하면 예제는 아래와 같이 된다.

A: 1 2 3 4 5 6 7 8 9 10
B: 8 2 9 1   4 6 7   10

여기서 B를 자세히 보면 1 4 6 7으로 연결된 선들을 살려야지 가장 길어지는 것을 볼 수 있다. 조금만 예제를 바꿔서 보면 가장 긴 증가하는 부분 수열을 구해야 함을 알 수 있다.

가장 긴 증가하는 부분 수열(LIS)

이 문제에서 입력 값이 10만, 50만으로 크기 때문에 O(n^2)의 속도를 가진 동적계획법을 이용한 방법으로는 해결할 수 없다. 이분탐색을 응용한 방법을 이용하여야 한다. 해당 부분은 https://seungkwan.tistory.com/8 에서 아주 잘 설명되어 있다. 간단히 LIS를 구하는 방법을 설명하자면, 배열을 하나 만들고 수열을 하나씩 확인하며 그 수가 배열의 제일 오른쪽 수보다 크면 뒤에 붙이고 작다면 이분탐색을 이용하여 해당 위치의 값을 대체한다. 이때 현재 구하는 LIS 인덱스를 같이 저장하여 나중에 실제 LIS 원소를 찾을 때 이용한다.

구해진 LIS는 자르지 않고 살려야 하는 전선들이다. 따라서 역으로 체크하여 나머지 부분을 출력하면 된다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cmath>
#include <climits>
#include <cctype>
using namespace std;

const int INF = 987654321;
const int MOD = 1000000000 + 7;
const int DIR[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

// ------------------------------------------------------

const int MAX_N = 100001;

int N;
pair<int, int> lines[MAX_N];
pair<int, int> answer[500001];
bool willBeRemoved[500001];
stack<int> s;

int LIS(void) {
	int length = 0;

	vector<int> perm;
	perm.push_back(lines[0].second);
	answer[0] = make_pair(0, lines[0].first);

	for (int i = 1; i < N; ++i) {
		int currentNum = lines[i].second;
		if (perm.back() < currentNum) {
			perm.push_back(currentNum);
			answer[i] = make_pair(perm.size() - 1, lines[i].first);
		}
		else {
			auto it = lower_bound(perm.begin(), perm.end(), currentNum);
            *it = currentNum;
			int index = it - perm.begin();
			answer[i] = make_pair(index, lines[i].first);
		}
	}
	return perm.end() - perm.begin();
}

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

	cin >> N;
	for (int i = 0; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		lines[i] = make_pair(a, b);
		willBeRemoved[lines[i].first] = true;
	}

	sort(lines, lines + N);

	int lisLength = LIS();
	cout << N - lisLength << endl;

	int num = lisLength - 1;
	for (int i = N - 1; i >= 0; i--) {
		if (answer[i].first == num) {
			willBeRemoved[answer[i].second] = false;
			num--;
		}
	}
	for (int i = 0; i < 500001; ++i) 
		if (willBeRemoved[i])
			cout << i << "\n";

	return 0;
}