[백준/BOJ] 백준 2532번 : 먹이사슬

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

2532번: 먹이사슬

정렬 뒤 range.erase(unique(range.begin(), range.end()), range.end())를 통해 중복된 값들을 지우고 왼쪽 범위가 작은 게 앞, 왼쪽 범위가 같다면 오른쪽 범위가 큰 게 앞에 오도록 정렬을 하고, 끝부터 확인해서 오른쪽 범위의 가장 긴 증가하는 부분 수열(n log n)을 찾는 방법으로 문제를 해결했다. 이때 upper_bound로 해서 같은 값이 check에 있어도 check에 넣는 방법으로 했다 (같은 값이 있어도 왼쪽 범위로 인해 먹이 사슬 조건에 만족하기 때문이다)

 

코드

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

int n;
vector<pair<int, int>> range;
vector<int> check;
vector<int>::iterator it;

bool cmp(pair<int, int> a, pair<int, int> b)
{
	if (a.first < b.first)
		return true;

	else if (a.first == b.first)
	{
		if (a.second >= b.second)
			return true;
	}

	return false;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int number;
		int l, r;

		cin >> number >> l >> r;

		range.push_back(make_pair(l, r));
	}

	//왼쪽 범위 기준으로 정렬
	sort(range.begin(), range.end());

	//중복되는 값 제거
	range.erase(unique(range.begin(), range.end()), range.end());

	//left가 작은게앞, left가 같다면 right가 큰게 앞에 오도록 정렬
	sort(range.begin(), range.end(), cmp);

	//끝부터 확인해서 오른쪽 범위의 가장 긴 증가하는 부분수열을 찾는다
	//upper_bound로 해서 range[i].second 값과 같은 값이 check에 있어도 check에 넣는 방법으로 한다 (같은 값이 있어도 left로 인해 먹이 사슬 조건에 만족하기 때문이다)
	for (int i = range.size() - 1; i >= 0; i--)
	{
		it = upper_bound(check.begin(), check.end(), range[i].second);

		if (it == check.end())
			check.push_back(range[i].second);

		else
			(*it) = range[i].second;
	}

	cout << check.size();

	return 0;
}