가장 긴 증가하는 부분 수열 5 (feat. 백준, 14003번)

가장 긴 증가하는 부분 수열 5
https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int N;
long long arr[1000000], tmp[1000000];
stack<pair<long long, int>> ans1;
stack<long long> ans2;
int binary_search(register int l, register int r, register long long value) {
	register int mid;
	while (l < r) {
		mid = (l + r) / 2;
		if (tmp[mid] < value)
			l = mid + 1;
		else
			r = mid;
	}
	return r;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;
	for (register int i = 0; i < N; ++i)
		cin >> arr[i];
	register int i = 1, j = 0;
	tmp[0] = arr[0];
	ans1.push(make_pair(tmp[0], 0));
	while (i < N) {
		if (tmp[j] < arr[i])
			tmp[++j] = arr[i], ans1.push(make_pair(arr[i], j));
		else {
			register int x = binary_search(0, j, arr[i]);
			tmp[x] = arr[i];
			ans1.push(make_pair(arr[i], x));
		}
		++i;
	}
	cout << j + 1 << "\n";
	while (!ans1.empty()) {
		auto v = ans1.top(); ans1.pop();
		if (v.second == j) {
			ans2.push(v.first);
			if (--j < 0)
				break;
		}
	}
	while (!ans2.empty())
		cout << ans2.top() << " ", ans2.pop();
	return 0;
}
// *&)*@*

굉장히 시간이 오래걸렸습니다.

총 3개의 배열이 필요로 합니다.

첫째로 arr1은 입력된 값을 받는 배열입니다.

둘째로 arr2는 입력된 값을 오름차순으로 치환시킨 배열입니다.

세번째로 arr3은 입력된 값이 arr2의 어느 인덱스에 들어갈지를 기록한 배열입니다.

 

위 내용을 설명하면 아래와 같습니다.

입력값 10이 arr2 arr3에 삽입됩니다.

입력값 20은 10보다 크기 때문에 arr2에 삽입되고 arr3은 다음 인덱스인 1을 저장합니다.

입력값 9는 10과 치환될 수 있는 값이므로 arr2의 첫값을 9로 치환하고 arr3은 치환된 인덱스 0을 입력합니다.

입력값 30은 20보다 크기 때문에 arr2에 삽입되고 arr3은 다음 인덱스인 2을 저장합니다.

입력값 21은 20과 치환될 수 있는 값이므로 arr2의 1번 인덱스 값을 21로 치환하고 arr3은 치환된 인덱스 1을 입력합니다.

입력값 50은 30보다 크기 때문에 arr2에 삽입되고 arr3은 다음 인덱스인 3을 저장합니다.

arr3의 제일 뒤에서부터 인덱스 순서대로 값을 빼면 '가장 긴 증가하는 부분 수열' 이 되게 됩니다.