[백준]브리징 시그널(3066)

문제 링크 : [백준]브리징 시그널(3066)

문제 설명

LIS문제입니다.

입력

T(테스트 케이스 갯수)
N(포트의 갯수, 1 <= N <= 40,000)
P_i(포트 번호)

3
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
9
5
8
9
2
3
1
7
4
6

출력

3
9
4

카테고리

#LIS

시간 복잡도 상한

O(N * logN)

해결 방법

1. 문제에서 주어진 포트의 순서를 가지고 최대한 엇갈리지 않는 경우를 만들려면 포트 번호가 증가하도록 하는 순서로 최대한 많이 연결하는 방법과 같습니다.
2. 즉 LIS로 풀면 됩니다.
3. N이 4만이기 때문에, N²이 아닌 N * logN으로만 풀면 됩니다.

   시간복잡도

   O(N * logN)

코드

#include<iostream>
#include<vector>
using namespace std;
int t,n,x;
vector<int>v;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    while(t--){
        v.clear();
        cin>>n;
        while(n--){
            cin>>x;
            if(v.empty()||v.back()<x)v.push_back(x);
            else v[lower_bound(v.begin(),v.end(),x)-v.begin()]=x;
        }
        cout<<v.size()<<"\n";
    }
}