[12015] 가장 긴 증가하는 부분수열2

카테고리 없음

[12015] 가장 긴 증가하는 부분수열2

___yejin 2017. 7. 6. 12:47

입력: 수열의 크기N(1 ≤ N ≤ 1,000,000), 수열을 나타내는 정수 Ai (1 ≤ Ai ≤ 1,000,000)
출력: 가장 긴 증가하는 부분 수열의 길이를 출력
실패한 소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int max(vector<int>, int, int, int, int, int);
void update(vector<int>&, int, int, int, int, int);

int main() {
	int N;
	scanf("%d", &N);
	vector<pair<int, int> > arr(N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i].first);
		arr[i].second = i;
	}

sort(arr.begin(), arr.end());

int h = (int)ceil(log2(N));
	vector<int> tree(1 << (h + 1), 0);

int maxLength;
	for (int i = 0; i < N; i++) {
		maxLength = max(tree, 1, 0, arr[i].second, 0, N - 1);
		if (i != 0 && arr[i - 1].first == arr[i].first) update(tree, 1, 0, N - 1, arr[i].second, maxLength);
		else update(tree, 1, 0, N - 1, arr[i].second, maxLength + 1);
	}

printf("%d\n", tree[1]);

return 0;
}

int max(vector<int> tree, int node, int left, int right, int start, int end) {
	if (left > end || right < start) return 0;
	if (left <= start && end <= right) return tree[node];

int a = max(tree, node * 2, left, right, start, (start + end) / 2);
	int b = max(tree, node * 2, left, right, (start + end) / 2 + 1, end);
	return (a > b ? a : b);
}

void update(vector<int>& tree, int node, int start, int end, int index, int key) {
	if (index < start || index > end) return;
	tree[node] = (tree[node] > key ? tree[node] : key);

if (start != end) {
		update(tree, node * 2, start, (start + end) / 2, index, key);
		update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, key);
	}
}

세그먼트 트리를 이용하여 구현하였지만 시간초과가 났다. 트리에 가장 긴 부분수열의 길이를 기록한다.

성공한 소스코드

세그먼트 트리가 아닌, 그냥 vector를 이용하여 구현하였다. lower_bound 함수를 사용했기 때문에 O(NlogN)일 것이라고 추정된다.

C++ 참고: auto http://yejin0730.tistory.com/40 / lower_bound http://yejin0730.tistory.com/41
문제참고: https://www.acmicpc.net/problem/12015
소스코드 참고: http://jason9319.tistory.com/113 / http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220791986409

저작자표시 (새창열림)