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

14003번: 가장 긴 증가하는 부분 수열 5

 

문제

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

14003번: 가장 긴 증가하는 부분 수열 5

 

 

풀이

그리고 N의 크기가 10^6이기 때문에 시간복잡도가 O(N^2)인 알고리즘으론 시간초과가 나게 된다. 따라서 시간복잡도가 O(NlogN)인 알고리즘을 사용해 12015번 문제와 같이 가장 긴 증가하는 부분 수열(LIS)을 구할 수 있다. 그러나 이 알고리즘으론 길이만 구할 수 있고 정확한 수열을 구할 수는 없기 때문에 추가 조정이 필요하다.

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

 

idx 배열을 만들어 수열의 각 원소가 LIS의 어느 위치에 들어갔는지(1부터) 기록한다. 그런 다음 idx 배열의 맨 뒤부터 LIS의 길이(N) 번째 위치에 들어간 원소를 찾는다. 같은 위치에 들어간 원소가 여러 개 있을 수 있는데, 이 경우 가장 빠르게 찾은 원소를 저장하고 다음 번째(N-1) 위치에 들어간 요소를 찾는다. 이를 1번째 위치에 들어간 원소를 찾을 때까지 반복한다. 원소를 모두 찾았다면 반대 순서로 다시 하나하나 출력해 주면 된다.

 

 

코드

#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}, LIS{x}, idx{1};
  for (int i = 1; i < n; i++) {
    cin >> x;
    v.push_back(x);
    if (LIS.back() < x) {
      LIS.push_back(x);
      idx.push_back(LIS.size());
    } else {
      auto it = lower_bound(LIS.begin(), LIS.end(), x);
      *it = x;
      idx.push_back(it - LIS.begin() + 1);
    }
  }
  int size = LIS.size();
  cout << size << '\n';
  vector<int> ans;
  for (int i = n - 1; i >= 0; i--)
    if (idx[i] == size) {
      ans.push_back(v[i]);
      size--;
    }
  for (int i = ans.size() - 1; i >= 0; i--)
    cout << ans[i] << ' ';
  cout << '\n';
  return 0;
}