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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이

이 문제는 O(n^2) 인 동적계획법을 이용해 풀면 시간초과가 나는 문제이다. 따라서 O(nlogn)인 이분탐색을 이용해 해결해야한다.
먼저 비어있는 vector에 수열에 들어갈 수 있는 숫자의 최댓값을 넣는다. 그럼 다음과 같은 상태가 될 것이다. v = {1000000}
이후 수열의 첫 원소를 v의 마지막원소와 비교한다. 수열의 원소가 더 크다면 벡터의 뒤에 추가한다. 수열의 원소가 작거나 같다면 lower_bound(v.begin(), v.end(), 수열의 원소)-v.begin()를 통해 v의 원소중 수열의 원소와 같거나 큰 원소의 가장 작은 인덱스를 구한다. 이후 그 위치의 값을 수열의 원소로 치환한다. 위의 과정을 끝까지 반복하면 v에는 가장 긴 증가하는 부분 수열이 담기게 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>

using namespace std;

int n;

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  vector<int> v = {1000000};

  for (int i=0; i<n; i++){
    int a;
    cin >> a;
    if (a > v.back()) v.push_back(a);
    else{
      int idx = lower_bound(v.begin(), v.end(), a) - v.begin();
      v[idx] = a;
    }
  }
  
  cout << v.size();
}