줄세우기

Problem link: https://www.acmicpc.net/problem/2631

전체 길이 - LIS 길이가 곧 답이 되는 문제이다.

제대로 이해하지 못한 것 같아서 죄책감에 LIS는 O(nlgn)으로 풀어줬다.

그대도 대략의 풀이 와꾸를 정리해보자면 다음과 같다.

애들이 엄청 띄엄띄엄 서 있다고 가정을 하고, 이 중에서 그냥 제자리에 가만히 있어도 되는 애들을 최소화 한다고 생각하자.

제자리에 있어도 되는 애들의 최대 명 수는 곧 LIS의 길이이고, 나머지 애들은 띄엄띄엄 있던 공간들에 채워넣으면 된다.

(한 명당 1회의 이동으로)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  size_t N;
  cin >> N;

  vector<size_t> STUDENTS(N, 0);
  for (auto& student : STUDENTS)
  {
    cin >> student;
  }

  // Solve
  vector<size_t> lis(1, STUDENTS[0]);
  for (size_t it = 1; it < STUDENTS.size(); ++it)
  {
    if (STUDENTS[it] > lis[lis.size() - 1])
    {
      lis.push_back(STUDENTS[it]);
    }
    else
    {
      size_t lb = lower_bound(lis.begin(), lis.end(), STUDENTS[it]) - lis.begin();
      lis[lb] = STUDENTS[it];
    }
  }

  cout << N - lis.size() << '\n';

  return 0;
}