[백준 / BOJ] C++ 1818 책정리

1818번: 책정리

 

문제

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

1818번: 책정리

 

 

풀이

책 번호를 오름차순으로 정렬하고자 하므로 가장 긴 이미 정렬되어 있는 책들은 놔두고 나머지 책들만 재배치를 하면 된다. 따라서 가장 긴 증가하는 부분 수열(LIS) 알고리즘을 사용해 LIS의 길이를 구하고, 책 수에서 LIS의 길이를 뺀 개수를 출력하면 된다.

 

N의 범위는 2 × 10^5이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 시간초과가 나므로 시간복잡도가 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;
  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 << n - v.size() << '\n';
  return 0;
}