백준 - 전깃줄 - 2 (2568) [C++]

이 문제는 이분 탐색을 이용한 LIS 알고리즘으로 풀었다.

 

이 문제에서 전깃줄의 개수는 최대 100,000개이므로 O(N^2) 알고리즘으로는 불가능하다.

즉, O(N log N) 이하의 알고리즘을 생각해야 한다.

 

전깃줄이 교차하는 것을 제거하는 것을 반대로 생각해보면 아무것도 없는 상태에서 전깃줄이 교차하지 않게 가장 많이 설치하는 문제와 같게 된다.

이는 전봇대 A의 순서로 정렬했을 때 랜덤하게 있을 전봇대 B의 순서에서 가장 긴 증가하는 부분 수열, LIS를 구하는 문제와 동일하게 된다.

 

DP를 이용한 LIS 문제는 O(N^2)이 걸리지만, 이분 탐색을 이용한 LIS 문제는 O(N log N) 시간이 걸리므로 충분히 시간 안에 풀 수 있다.

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

int N;
vector<pair<int, int>> lines;
map<int, int> bToA;
bool isUsed[500001];

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b;

		cin >> a >> b;
		lines.push_back({ a, b });
		bToA[b] = a;
	}

	sort(lines.begin(), lines.end());
	vector<int> arr;
	for (pair<int, int> &temp : lines) {
		arr.push_back(temp.second);
	}

	vector<int> answer;
	vector<int> indexRecord;
	for (int i = 0; i < N; i++) {
		int present = arr[i];

		if (answer.empty()) {
			answer.push_back(present);
			indexRecord.push_back(0);
		} else {
			if (answer.back() < present) {
				indexRecord.push_back(answer.size());
				answer.push_back(present);
			} else {
				int index = lower_bound(answer.begin(), answer.end(), present) - answer.begin();
				
				answer[index] = present;
				indexRecord.push_back(index);
			}
		}
	}

	int initIndex = answer.size() - 1;
	
	for (int i = indexRecord.size() - 1; i >= 0; i--) {
		int index = indexRecord[i];

		if (index == initIndex) {
			initIndex--;
			int realNum = arr[i];
			isUsed[realNum] = true;
		}
	}

	vector<int> result;
	for (pair<int, int> &temp : lines) {
		int b = temp.second;

		if (!isUsed[b]) {
			result.push_back(temp.first);
		}
	}

	cout << result.size() << '\n';
	for (int r : result) {
		cout << r << '\n';
	}
	
	return 0;
}