[백준] 12738-가장 긴 증가하는 부분 수열 3(C++)

문제링크: https://www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

 

 

대표적인 이분탐색 LCS문제입니다.

아래 문제와 동일하여 설명은 대체합니다.

https://gusdnr69.tistory.com/279

[백준] 1365-꼬인 전깃줄(C++)

 

 

문제풀이 

 

1.  일반적인 구현방식으로 해결

 

 

#include <iostream>
#include <vector>
using namespace std;

int n;
int arr[1000000];
vector <int> v;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 0; i < n; i++) {
		if (v.size() == 0 || v[v.size() - 1] < arr[i]) v.push_back(arr[i]);
		else {
			int left = 0;
			int right = v.size();

			while (left <= right) {
				int mid = (left + right) / 2;
				if (v[mid] >= arr[i]) right = mid - 1;
				else left = mid + 1;
			}
			v[left] = arr[i];

		}


	}
	cout << v.size() << endl;
	return 0;
}