본문으로 바로가기

LIS(Longest Increasing Subsequence)를 O(NlogN) 시간 복잡도를 이용하여 구하는 방법은 이진 탐색을 사용하는 것이다. 임의의 원소가 들어왔을 경우 이진 탐색을 통해 그보다 같거나 큰 수를 선택하여 최적의 LIS를 구하기 위해 원소를 계속 교체해주는 방법이다.

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

int n;
vector<int> v;

int main() {
  scanf("%d", &n);

  int x;
  while (n--) {
    scanf("%d", &x);

    if (v.empty() || v.back() < x) {
      v.push_back(x);
    } else {
      auto it = lower_bound(v.begin(), v.end(), x);
      *it = x;
    }
  }

  printf("%d\n", (int)v.size());
  return 0;
}

댓글을 달아 주세요