[BOJ/Platinum 4] 백준 2532 먹이사슬(C++)

문제 링크

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

 

문제

1부터 N까지 번호가 붙여져 있는 N마리 서로 다른 동물이 있다. 모든 동물은 동일한 하나의 수평선 상에서 연속된 구간 내에서 활동한다. 이 구간을 그 동물의 활동영역이라 한다. 동물의 활동영역은 구간의 왼쪽 위치와 오른쪽 위치 쌍으로 나타낸다. 예를 들어, 7마리 동물의 활동영역이 다음 그림과 같다고 하자. 각 동물의 활동 영역은 선분으로 나타내어져 있다. 아래에서 동물 1의 활동영역은 (2, 4), 동물 2의 활동영역은 (6, 10), ..., 동물 7의 활동영역은 (3, 4)이다.

 

활동영역이 (x1, x2)인 동물 i와 (x3, x4)인 동물 j에 대하여, 다음 세 조건 중 하나를 만족하면 i가 j보다 먹이사슬에서 상위에 있다고 한다. 

• 조건 1: x1 < x3 이고 x2 > x4
• 조건 2: x1 = x3 이고 x2 > x4  
• 조건 3: x1 < x3 이고 x2 = x4 

 

동물들의 집단에 대하여 다음 조건을 만족하면서 모든 동물들을 나열 할 수 있으면, 이 집단은 먹이사슬 구조를 가진다고 말한다.

조건: 나열된 각 동물은 뒤에 나오는 모든 동물보다 먹이사슬에서 상위에 있다. 

단, 하나의 동물로 이루어진 집단도 먹이사슬 구조를 가진다고 말한다. 먹이사슬 구조를 가지는 동물 집단의 크기는 이 집단에 속하는 동물의 수로 정의한다. 

동물들의 활동영역이 주어질 때, 먹이사슬 구조를 가지는 동물 집단의 최대 크기를 구하는 프로그램을 작성하시오. 

앞의 그림 예에서 먹이사슬 구조를 가지는 동물 집단의 예로 {1}, {2, 4}, {2, 6}, {1, 3}, {1, 3, 7}, ... 등이 있다. 집단 {1, 3, 7}에서  3은 1보다 상위이고 1은 7보다 상위로서 먹이사슬 구조를 가지는 최대 크기의 집단이다. 최대 크기 집단은 하나 이상일 수 있다.

 

입력

첫 번째 줄에는 동물의 수를 나타내는 N (1 ≤ N ≤ 500,000)이 주어진다. 다음 각 줄에 동물의 번호, 동물의 활동영역의 왼쪽 위치 L, 오른쪽 위치 R이 빈 칸을 사이에 두고 나온다. L, R은 1 이상 1,000,000,000 이하의 양의 정수이다.

 

출력

먹이사슬 구조를 가지는 최대 집단의 크기를 출력한다.

 

예제 입력 1

7
1 2 4
3 1 5
4 7 8
6 9 10
2 6 10
5 5 7
7 3 4

예제 출력 1

3

 

알고리즘 분류

• 정렬
• 다이나믹 프로그래밍
• 이분 탐색

 

풀이

L을 오름차순, L이 같다면 R을 기준으로 내림차순 정렬한다.

주어진 조건에서 L, R이 모두 같은 경우는 먹이사슬을 따질 수 없기 때문에, 중복되는 활동영역을 제거한다.

그리고 R값을 기준으로 LIS를 구한다. 이 때, R값은 중복되어도 상관 없으므로 upper_bound로 이분 탐색을 진행한다.

LIS를 구했다면, LIS에 포함되는 활동영역의 개수를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, I;
vector<pair<int, int> > Reigns;
int Answer;

void input() {
	cin >> N;
	Reigns.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> I >> Reigns[i].first >> Reigns[i].second;
		Reigns[i].second *= -1;
	}
}

int findScopes() {
	vector<pair<int, int> > Result;
	vector<int> DP;
	vector<int> Indices;
	vector<int> PrevIndices(N, -1);

	for (int i = 0; i < N; i++) {
		auto IT = upper_bound(DP.begin(), DP.end(), Reigns[i].second);
		int Index = IT - DP.begin();

		if (IT == DP.end()) {
			DP.push_back(Reigns[i].second);
			Indices.push_back(i);
		}
		else {
			*IT = Reigns[i].second;
			Indices[Index] = i;
		}

		if (Index > 0) {
			PrevIndices[i] = Indices[Index - 1];
		}
	}

	int Current = Indices.back();
	while (Current != -1) {
		Result.push_back(Reigns[Current]);
		Current = PrevIndices[Current];
	};

	reverse(Result.begin(), Result.end());

	return (int)Result.size();
}

bool comp(pair<int, int> A, pair<int, int> B) {
	if (A.first == B.first) {
		return (A.second < B.second);
	}

	return (A.first < B.first);
}

void settings() {
	sort(Reigns.begin(), Reigns.end(), comp);
	Reigns.erase(unique(Reigns.begin(), Reigns.end()), Reigns.end());
	Answer = findScopes();
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
    FASTIO

	input();
	settings();
    printAnswer();

    return 0;
}