[구름LEVEL] JMOS

level.goorm.io/exam/49109/jmos/quiz/1

구름LEVEL

---

 

-풀이-

꼬여있는관계를 없애기 위해 자원을 반납해야하는 최소한의 프로그램 개수를 구하는 문제이다.

이문제는 꼬여있는 최소한을 없애는것== 전체에서 가장 긴 증가하는 수열의 개수를 빼주는것과 같다.

따라서 가장 긴 증가하는 수열의 개수를 구해준 뒤, 전체 개수에서 빼주면 된다.

 

-시간 복잡도-

전체적으로 N번을 돌며, lower_bound를 실행하기 때문에 O(NlogN)이 된다.

 

-코드-

 

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

vector<int> v;
int n;

int main() {
	cin>>n;
	
	for(int i=0;i<n;i++){
		int data;
		cin>>data;
		
		if(v.empty()||v.back()<data){
			v.push_back(data);
		}
		else{
			int ind=lower_bound(v.begin(),v.end(),data)-v.begin();
			v[ind]=data;
		}
	}
	cout<<n-v.size()<<"\n";
	
	return 0;
}