(12015) 가장 긴 증가하는 부분 수열 2

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

단계별로 풀어보기

25단계(이분 탐색) 7번째

 

 

 

DP로 푼 적 있는 문제지만 N의 범위가 커져서 O(N^2)로는 시간 초과가 난다.

의외로 이분 탐색이 쓰이는 굉장히 놀라운 문제. 벡터 ans의 정의를 아래와 같이 두자.

ans[i]: 지금까지 탐색한 원소들로 만든 길이가 i인 부분 증가 수열의 마지막 원소의 최소값

이때 새로운 수 x가 들어오면 lower_bound로 인덱스를 찾아 아래 두가지 경우 중 하나가 일어난다.

1) 인덱스가 ans범위보다 클 때: 기존 최장 LIS의 마지막 원소 값보다 x가 크다는 의미이므로 기존 LIS에 x를 붙여 길이가 1 증가한 새로운 LIS를 만들 수 있다. 따라서 ans 뒤에 push_back으로 새로 덧붙인다.

2) 인덱스가 중간일 때: 나온 값이 idx라고 하면, ans[idx-1]<x≤ans[idx]이다. 부분 증가 수열의 길이가 똑같다면 마지막 원소의 값이 작은 것이 이후 LIS를 만들 때 더 유리하므로 ans[idx]를 더 작은 값인 x로 교체한다.

순회가 끝났을 때 ans의 길이가 가능한 LIS의 최대 길이가 된다. 주의해야 할 점은 ans는 LIS의 구성 원소를 나타내는 것이 아니다. 앞서 설명했듯 ans[i]는 길이가 i인 부분 증가 수열의 마지막 원소의 최소값을 의미한다. 따라서 LIS를 이루는 수열을 요구할 땐 역추적이 필요한데 아마 역추적 단계에서 나올 것이다.

 

입력받은 수 N개에 대해 한 번씩 이분 탐색을 시행하므로 시간 복잡도는 O(N log N)이다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> ans;
  
  for(int i=0;i<n;i++){
    int t;
    
    cin >> t;
    
    int idx= lower_bound(ans.begin(), ans.end(), t)-ans.begin();
    
    if(idx==ans.size())  ans.push_back(t);
    else  ans[idx]= t;
  }
  
  cout << ans.size();
  
  return 0;
}