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

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

반도체 회로가 얽이지 않기 위해서는
우리는 해당 회로의 LIS를 구하면 된다

이 문제는 내가 이전에 풀었던 LIS 문제를 dp가 아닌 이분탐색으로 푸는 문제이다

해당 이미지를 보고 우리는 LIS즉 이전 인덱스가 현재 인덱스보다 커지지 않게 해주면 된다

 

이문제의 풀이는 
첫번째로 LIS 배열을 만들어주고 LIS는 무조건 1이상 일것이다 이에 LIS[0]에 arr[0]를 넣어준다

그후 우리는 2

가지 규칙으로 해당 문제를 풀어주면 된다
현재 내가 보는 숫자가 LIS의 가장 나중 인덱스의값보다 크면  그 나중인덱스 + 1 위치에 해당 수를 넣어주고

작을 시에는 해당 LIS 배열에서 해당 수가 들어갈 적절한 위치를 이분탐색으로 찾아서 해당 위치에 해당수를넣어주면된다

#include <iostream>

using namespace std;

int arr[40000];
int lis[40000];

int binarySearch(int left, int right, int target) {
	int mid = 0;
	while (left < right) {
		mid = (left + right) / 2;
		if (lis[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return right;
}
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int j = 0;
	int i = 1;

	lis[0] = arr[0];

	while (i < n) {
		if (lis[j] < arr[i]) {
			lis[j + 1] = arr[i];
			j += 1;
		}
		else {
			int pos = binarySearch(0, j, arr[i]);
			lis[pos] = arr[i];
		}

		i += 1;
	}

	cout << j + 1;
}