백준 12015. 가장 긴 증가하는 부분 수열 2 - 문제풀이 (c++) (dp)

🔎 12015. 문제 보기

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

💡 문제 풀기 전

가장 긴 증가하는 부분 수열 이 문제와 비슷해보인다.
하지만 수열의 크기가 1,000,000로 시간 복잡도가 O(n^2)인 로직을 이용하면 시간을 통과하지 못한다. 그래서 O(nlog(n))로직을 생각해야 했다.

📝 코드 보기

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1111111];
int cache[1111111];
vector<int> v;

void binary_search(int x) {
	int left=0, right=v.size(), mid=0;
	int index=1e9;
	while(left<=right) {
		mid=(left+right)/2;
		int num = v[mid];
		if(num >= x) {
			if(index> mid) {
				index=mid;
			}
			right=mid-1;
		} else {
			left=mid+1;
		}
	}
	
	v[index]=x;
}

void solve() {
	v.push_back(a[0]);
	
	for(int i=1; i<n; i++) {
		if(v.back() < a[i]) {
			v.push_back(a[i]);
		} else {
			binary_search(a[i]);
		}
	}
}

int main() {
	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> a[i];
	}
	
	solve();
	cout << v.size() << "\n";
	for(int i=0; i<v.size(); i++) {
		cout << v[i] << " ";
	} 
	return 0;
} 

🎈 코드 풀이 및 관련 개념

시간 복잡도: O(nlog(n))

시간 n은 수열 A를 탐색하는 시간
시간 log(n)은 이분 탐색을 통하여 벡터의 값을 바꾸는 시간이다.

방법

예를 들어 {1, 3, 7, 5}의 수열이 있다.
여기서 lis는 {1, 3, 7} 또는 {1, 3, 5}가 있다. 하지만 {1, 3, 7}보다 {1, 3, 5}가 무조건 더 좋은 수열이다. 그다음 수열에 {6}이 추가되면 {1, 3, 7, 6}은 안되지만 {1, 3, 5, 6}은 가능하다.

그래서 벡터를 이용해 하나의 값을 넣은 후 벡터 맨 뒤의 값(처음에는 배열의 첫 번째 값)과 주어진 수열의 값을 비교해서 각각의 로직을 실행한다.