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

12738번: 가장 긴 증가하는 부분 수열 3

 

문제

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

12738번: 가장 긴 증가하는 부분 수열 3

 

 

풀이

12015번 가장 긴 증가하는 부분 수열 2 문제와 완전히 같은 알고리즘으로 풀 수 있다. 수열을 이루는 수의 크기에 변화가 있지만 int 범위 안이고 시간복잡도 자체에는 바뀔 부분이 없다. 12015번 해설은 아래 링크를 참고하자.

[12015번 가장 긴 증가하는 부분 수열 2 문제] | [12015번 가장 긴 증가하는 부분 수열 2 풀이]

 

 

코드

#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;
}