[LIS] BOJ 12015 가장 긴 증가하는 부분 수열 2

www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

문제 해결 알고리즘

 

다이나믹 프로그래밍을 이용해서 풀면 시간초과가 난다 (O($ \mathrm{n^2}$)) 그러므로 이분탐색 (O($ \mathrm{ nlogn}$))으로 문제를 풀어야한다.

 

lower_bound : 해당 원소보다 큰 작은 원소를 찾음. (이분탐색)

 

1. 벡터(v)에 주어진 원소들을 입력받는다.

2. 벡터(vt)에 가장 작은 원소 (-1)를 넣는다.

3. 만약 v[i]의 크기가 vt의 마지막 원소보다 크기가 크다면 그 원소를 vt의 뒤에 두고 갯수(cnt)를 하나 더해준다.

    작다면, lower_bound를 이용해서 그 원소에 해당하는 위치의 원소와 바꾼다.

4. 갯수(cnt)를 출력한다.

 

소스 코드

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

int main(){
  int num; cin >> num;
  int cnt = 0;
  vector<int> v(num);
  vector<int> vt(num);

  for(int i=0;i<num;i++){
    cin >> v[i];
  }

  vt.push_back(-1);

  for(int i=0;i<num;i++){
    if(vt.back() < v[i]){
      vt.push_back(v[i]);
      cnt++;
    }
    else {
      auto it = lower_bound(vt.begin(), vt.end(), v[i]);
      *it = v[i];
    }
  }

  cout << cnt;
}