백준 1365 / C++ / 이분탐색 / LIS

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

이 문제는 이분탐색으로 LIS를 찾는 문제이다 이를 해결하는 과정은 해당 카테고리의 이전 게시물들을 참고하면 된다

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> lis;
int binary_search(int target) {
	int start = 0; 
	int end = lis.size() - 1;
	int mid = 0;
	while (start < end) {
		mid = (start + end) / 2;
		if (lis[mid] < target) {
			start= mid+1;
		}
		else {
			end = mid ;
		}
	}
	return start;
}

int main() {

	cin >> n;
	int idx = 0;
	int tmp;
	cin >> tmp;
	lis.push_back(tmp);
	for (int i = 1; i < n; i++) {
		cin >> tmp;
		if (tmp > lis[idx]) {
			lis.push_back(tmp);
			idx++;
		}
		else {
			lis[binary_search(tmp)] = tmp;
		}
	}

	cout << n-lis.size();

}