2568 ์ „๊ธฐ์ค„

์•Œ๊ณ ๋ฆฌ์ฆ˜(LIS)

1. LIS๋ฅผ ๊ตฌํ•˜๋ฉด ๊ทธ๊ฒƒ๋“ค์ด ๊ฒน์น˜์ง€ ์•Š๊ณ  ์ตœ๋Œ€๋กœ ์—ฐ๊ฒฐ๊ฐ€๋Šฅํ•œ ์ „๊นƒ์ค„๋“ค์ด๋‹ค.
2. ๋”ฐ๋ผ์„œ LIS๋ฅผ ๊ตฌํ•˜๊ณ  ์ „์ฒด ์ „๊นƒ์ค„์—์„œ LIS๋ฅผ ๋นผ๋ฉด ๋นผ์•ผํ•˜๋Š” ์ „๊นƒ์ค„์˜ ์ˆ˜์™€ ์ „๊นƒ์ค„์˜ ์ข…๋ฅ˜๊ฐ€ ๋‚˜์˜ค๊ฒŒ ๋œ๋‹ค.

์ฝ”๋“œ

#include <bits/stdc++.h>
#define MAX_WIRE 100001
 
using namespace std;
 
struct Wire {
	int a;
	int b;
	bool check;
	bool operator <(Wire s) {
		return a < s.a;
	}
};
 
Wire wire[MAX_WIRE];
int numOfWire, length[500001], save[500001], numOfSave;
 
void LIS();
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	cin >> numOfWire;
	for (int i = 0; i < numOfWire; i++)
		cin  >> wire[i].a >> wire[i].b;
 
	sort(wire, wire + numOfWire);
 
	LIS();
}
 
void LIS() {
	int result = 0, index = 0;
	for (int i = 0; i < numOfWire; i++) {
		int *lb = lower_bound(save, save + numOfSave, wire[i].b);
 
		length[wire[i].a] = lb - save + 1;
		*lb = wire[i].b;
 
		if (length[wire[i].a] ==  numOfSave + 1)
			numOfSave++;
 
		if (result < length[wire[i].a]) {
			result = length[wire[i].a];
			index = i;
		}
	}
 
	cout << numOfWire - result << "\n";
	for (int i = index; i >= 0; i--) {
		if (result <= 0)
			break;
		if (length[wire[i].a] == result) {
			wire[i].check = true;
			result--;
		}
	}
	for (int i = 0; i < numOfWire; i++)
		if (!wire[i].check)
			cout << wire[i].a << "\n";
}