BOJ 2532 - 먹이사슬 (LIS)

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

 

<문제설명>

각 요소마다 구간이 주어질 때, 어떤 구간이 한 구간을 완전 감쌀 수 있다면 먹이사슬 상 상하관계가 나뉜다고 한다. 가장 긴 먹이사슬의 크기를 구하라

 

<풀이>

priority queue를 이용해서 풀고자 했지만 잘 보이지 않는다. 2차원 평면에 그래프를 그려보면 형태가 눈에 보일 것.

 

x값 증가, y값 감소하도록 {x,y}를 정렬한다면 y값들만 봤을 때 가장 긴 최장단조감소부분수열의 길이를 구하면된다.

 

lower_bound대신 upper_bound를 쓰면 된다.

 

(같은 구간은 빼주고 생각해야 함에 주의)

 

<코드>

int n;
vector<P> a;

int main() {
	FAST; cin >> n;
	for (int i = 0,x,y,z; i < n; i++) {
		cin >> x >> y >> z;
		a.push_back({ y,z });
	}
	sort(a.begin(), a.end(), [](P p1, P p2) {
		if (p1.first == p2.first) return p1.second > p2.second;
		return p1.first < p2.first; });

	vector<int> v(1,-1e9-1);
	for (int i = 0,x; i < a.size(); i++) {
		x = -a[i].second;
		if (i > 0 && a[i].first == a[i - 1].first && a[i].second == a[i - 1].second) continue;
		if (v.back() <= x) v.push_back(x);
		else *upper_bound(v.begin(), v.end(), x) = x;		
	}
	cout << v.size()-1 << '\n';
}