[백준 2568] 전깃줄 - 2

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

---

해설

일단, https://www.acmicpc.net/problem/14003 이 문제랑 https://www.acmicpc.net/problem/2565 랑 거의 유사하다.

이 문제 안에는 저 두문제가 섞인 문제임에도 골드 2다.

14003은 골드 1이고 문제는 비슷하게 풀리는 데 왜 그런지 잘 모르겠다.

그전에 풀었던 두 문제의 짬뽕이기 때문에 이번에는 해설을 진행하지 않겠다.

 

˙˙˙

 

 

소스코드

 

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int p[1000001];

vector<int> arr;
vector<int> memo;
vector< pair<int, int> > vp;

int main() {
	cin >> n;
    
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		vp.push_back({ a,b });
	}
	sort(vp.begin(), vp.end());
	arr.push_back(vp[0].second);
    
	for (int i = 1; i < n; i++) {
		if (arr.back() < vp[i].second) {
			arr.push_back(vp[i].second);
			p[i] = arr.size()-1;
		}
		else {
			auto it = lower_bound(arr.begin(), arr.end(), vp[i].second);
			*it = vp[i].second;
			p[i] = it - arr.begin();
		}
	}
	int cnt = arr.size();
	cout << n - cnt << '\n';
	cnt--;
	for (int i = n - 1; i >= 0; i--) {
		if (p[i] == cnt) {
			cnt--;
			continue;
		}
		memo.push_back(vp[i].first);
	}

	for (int i = memo.size() - 1; i >= 0; i--)
		cout << memo[i] << '\n';
}