백준 12015, 가장 긴 증가하는 부분 수열 2

문제

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

풀이

내 머리로 풀 수 있는 문제는 아닌 것 같아서 그냥 컨셉을 보고 풀었다. 신기했다. 다만 lowerbound 구현이랑 정확한 이해, 이거 구현을 제대로 알아야 할 것 같다. 나중에 세그먼트 트리로 하는 거랑 빨리한 사람 코드도 보면 좋을 것 같다.

실수

• 범위 체크 안해서 런타임 에러남
• lowerbound 구현 느림

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>

using namespace std;

vector<int> input(1100000, 0);
vector<int> dp(1100000, 0);
vector<int> arr;

int lowerbound_bs(int s, int e, int target) {

	while (s < e) {

		int mid = (s + e) / 2;

		if (target <= arr[mid])
			e = mid;

		else
			s = mid + 1;

	}

	return s;

}

int main() {

	int n;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {

		scanf("%d", &input[i]);

	}

	arr.push_back(-1 * 2e9);

	for (int i = 0; i < n; i++) {

		int s = lowerbound_bs(0, arr.size(), input[i]);

		if (s == arr.size())
			arr.push_back(input[i]);

		else if (arr[s] > input[i])
			arr[s] = input[i];

	}

	printf("%d", arr.size() - 1);

	return 0;

}