[백준] 12015번 가장 긴 증가하는 부분 수열 2 C++ 코드

코드

// 데이터의 크기가 100만 => O(N^2)은 시간 내에 불가
// O(NlogN) 풀이법
#include <iostream>
#include <algorithm>

using namespace std;
int n, a[1000003], num, res;
int main() {
  cin >> n;
  for(int i = 0; i < n; i++) {
      cin >> num;
      auto k = lower_bound(a, a+ res, num);
      if(*k == 0) res++;
      *k = num;
  }
  
  cout << res << '\n';
  return 0;
}

가장 긴 증가하는 부분 수열 (11053번) 문제와 유사하지만 데이터 크기가 차이난다. 데이터 크기가 100만이기 때문에 O(NlogN)으로 해결해야 한다. lower_bound를 이용해, 들어오는 값의 위치를 찾고 만약 새로 들어오는 값이면 res에 1을 더해준다. 그리고 작은 값이 들어오면 그 자리를 대체하게 한다. 이 풀이는 원본 배열을 확보하기 어렵다는 단점이 있다. 원본 배열(원본 증가하는 부분 수열) 을 찾으려면 다른 처리를 해주어야 한다. 이 경우에는, pair 배열에 값을 넣어주고, 길이에 맞는 값을 찾아주면 된다.