[BOJ/Platinum 4] 백준 2995 생일(C++)

문제 링크

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

 

문제

상근이는 생일 선물로 구간 N개를 받았다. 여기서 말하는 구간이란 수의 구간이며, [A, B]와 같은 구간이다. 구간을 어떻게 선물로 받았는 지는 잘 모르겠지만, 진짜로 그 수학에 나오는 구간이다.

상근이는 자신이 가지고 있는 구간 중에서 아래와 같은 조건을 만족하는 가장 긴 서로 다른 구간의 수열을 찾으려고 한다.

수열에 포함되는 모든 구간은 다음 위치에 있는 구간을 포함해야 한다.

가장 긴 수열을 찾는 프로그램을 작성하시오.

 

입력

첫째 줄에 구간의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개 줄에는 각 구간 [A,B]의 정보 A와 B가 주어진다. (1 ≤ A < B ≤ 1,000,000)

 

출력

첫째 줄에 수열의 길이 K를 출력한다. 다음 K줄에는 수열에 포함되는 구간을 입력 형식과 같이 한 줄에 하나씩 순서대로 출력한다.

 

예제 입력 1

5
10 30
20 40
30 50
10 60
30 40

예제 출력 1

3
10 60
30 50
30 40

예제 입력 2

3
3 4
2 5
1 6

예제 출력 2

3
1 6
2 5
3 4

예제 입력 3

6
1 4
1 5
1 6
1 7
2 5
3 5

예제 출력 3

5
1 7
1 6
1 5
2 5
3 5

 

알고리즘 분류

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

 

풀이

먼저 정렬을 해야 한다. 모든 구간은 다음 위치의 구간을 포함해야 하므로, A를 오름차순, A가 같다면 B를 기준으로 내림차순 정렬한다.

그리고 B값을 기준으로 LIS를 구한다. 이 때, B값은 중복되어도 상관 없으므로(이전 B값과 다음 B값이 같다면, A를 기준으로 오름차순 정렬이 되어 있기 때문에 이전 구간은 반드시 다음 구간을 포함하게 된다.) upper_bound로 이분 탐색을 진행한다.

또한, LIS로 도출되는 구간을 모두 구해야 하므로, 현재 Index의 이전 Index를 기록해둔다.

LIS를 구했다면, 마지막 Index부터 역순으로 LIS에 포함되는 구간들을 찾고 reverse()로 반전시킨다.

 

코드

#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;
vector<pair<int, int> > Scopes;
vector<pair<int, int> > Answer;

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

vector<pair<int, 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(), Scopes[i].second);
		int Index = IT - DP.begin();

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

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

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

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

	return Result;
}

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(Scopes.begin(), Scopes.end(), comp);
	Answer = findScopes();
}

void printAnswer() {
	cout << (int)Answer.size() << "\n";
	for (int i = 0; i < (int)Answer.size(); i++) {
		cout << Answer[i].first << " " << -Answer[i].second << "\n";
	}
}

int main() {
    FASTIO

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

    return 0;
}