Problem

Solution

• 남아있는 모든 전깃줄이 서로 교차하지 않는 조건은 전봇대 B에서 LIS(Longest Increasing Sequence)를 찾고 나머지 위치의 전깃줄을 없애는 경우와 같다.
• LIS를 구하는 유명한 알고리즘 두 가지가 있다. Dynamic Programming을 이용하여 O(N2)이
  걸리는 알고리즘과 Binary Search를 이용하여 O(NlogN)이 걸리는 알고리즘이다. 문제의
  조건이 N ≤ 100000이므로 두 번째 알고리즘을 이용해야한다.

  배열 [8, 2, 9, 1]의 LIS길이를 Binary Search를 통해 구하는 알고리즘을 살펴보자.
  insert 8 > arr: [8]
insert 2 > arr: [2]
insert 9 > arr: [2, 9]
insert 1 > arr: [1, 9]
  ∴ len(LIS) = 2

• 일반적인 알고리즘을 이용할 경우 LIS의 길이만 구할 수 있을뿐 LIS는 직접적으로 구할 수 없다.
  LIS를 직접적으로 구하는 알고리즘은 https://yhwan.tistory.com/21 님의 블로그 사진을 참고하였다.

  배열 [8, 2, 9, 1]의 LIS를 구해보자.
  insert 8 > arr: [8] idx: [1]
insert 2 > arr: [2] idx: [1, 1]
insert 9 > arr: [2, 9] idx: [1, 1, 2]
insert 1 > arr: [1, 9] idx: [1, 1, 2, 1]
  idx배열에서 첫번째로 나오는 인덱스 찾기 > idx : [1, 1, 2, 1]
  ∴ LIS = [2, 9]

• 전봇대 B에서 찾은 LIS와 전봇대 A의 위치를 mapping하기 위해 map 라이브러리를 이용하였다.

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

int N;
vector<pair<int, int>> arr; // 전봇대 (A, B)를 저장하는 배열
vector<int> sarr; // 전봇대 A를 정렬했을 때의 전봇대 B 배열
map<int, int> m; // (key, value) == 전봇대 (B, A)

int main(){
	scanf("%d", &N);
	arr = vector<pair<int, int>>(N);
	sarr = vector<int>(N);
	
	for(int i=0; i<N; i++){
		int key, value;
		scanf("%d %d", &value, &key);
		arr[i].first = value;
		arr[i].second = key;
		m[key] = value;
	}
	
	sort(arr.begin(), arr.end());
	
	for(int i=0; i<N; i++){
		sarr[i] = arr[i].second;
	}
	
	vector<int> v; // 이분탐색을 진행하는 배열
	vector<int> iarr; // 배열에 추가되는 숫자의 인덱스를 저장하는 배열
	
	for(int i=0; i<N; i++){
		if(i == 0){
			v.push_back(sarr[i]);
			iarr.push_back(1);
			continue;
		}
		int idx = lower_bound(v.begin(), v.end(), sarr[i]) - v.begin();
		int len = v.size();
		// 추가하는 숫자가 가장 마지막 숫자보다 크다면
		if(idx == len) v.push_back(sarr[i]);
		else v[idx] = sarr[i]; // 않다면 교체
		iarr.push_back(idx + 1); // 인덱스 배열에 인덱스 넣기
	}
	
	int len = v.size();
	vector<int> ans(len); // LIS 배열
	// LIS를 구하는 과정
	for(int i=N-1, n=len; i>=0; i--){
		if(iarr[i] == n)
			ans[--n] = sarr[i];
	}
	// LIS에 속하는 숫자를 제하는 과정
	for(int i=0; i<len; i++){
		m[ans[i]] = -1;
	}
	
	printf("%d \n", N - len);
	for(int i=0; i<N; i++){
		int key = sarr[i];
		if(m[key] == -1) continue;
		printf("%d \n", m[key]);
	}
}

Result

• 전봇대 A를 기준으로 전봇대 B의 LIS를 구하였는데 전봇대 B를 기준으로 전봇대 A의 LIS를
  구했으면 map 라이브러리를 사용할 필요가 없었을 것 같다.