[백준 / BOJ] C++ 12015 가장 긴 증가하는 부분 수열 2

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

 

문제

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

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

 

 

풀이

LIS 시리즈 문제 중 하나로 N의 범위가 10^5 이상인 문제에선 사용이 불가능한 시간복잡도가 O(N^2) 알고리즘으로는 풀리지 않는 문제다. 이분 탐색을 사용해 시간복잡도가 O(NlogN)인 알고리즘을 사용해 풀었다.

 

첫 번째 원소는 벡터에 넣어놓고, 다음 원소(편의상 x)부터 비교를 시작한다. 만약 x가 백터의 가장 뒤 원소보다 크다면 push_back을 해준다. 이러면 벡터의 크기가 1 증가했고 LIS의 크기도 증가했다고 볼 수 있다. 만약 x가 가장 뒤 원소보다 작거나 같다면 lower_bound 함수를 사용해 x보다 크거나 같은 첫 번째 원소가 등장하는 위치에 x를 넣어준다. 위 과정을 반복한 다음 벡터의 크기를 출력하면 된다.

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, x;
  cin >> n >> x;
  vector<int> v{x};
  for (int i = 1; i < n; i++) {
    cin >> x;
    if (v.back() < x)
      v.push_back(x);
    else
      *lower_bound(v.begin(), v.end(), x) = x;
  }
  cout << v.size() << '\n';
  return 0;
}