[백준 / BOJ] C++ 3745 오름세

3745번: 오름세

 

문제

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

3745번: 오름세

 

 

풀이

수열이 주어졌을 때 점차 증가하는 부분 수열을 오름세라 하고 가장 긴 오름세를 찾는 문제다. 즉, 가장 긴 증가하는 부분 수열을 구하는 문제다. 범위가 10^5이므로 시간복잡도가 O(NlogN)인 알고리즘을 사용해 풀어야 한다. O(NlogN)으로 푸는 법은 아래 링크에 설명되어 있다.

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

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, x;
  while (cin >> n) {
    cin >> 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;
}