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

문제

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

접근 방법

아무 책이나 꺼내서 아무 곳에 꽂을 수 있다는 것은 정렬된 책을 미리 위치해두고 그 사이에 책을 꽂아 넣으면 되는 것입니다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int book;
int lisArr[200000], lis = 1;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N >> lisArr[0];

    for (int i = 1; i < N; ++i)
    {
        cin >> book;

        int idx = lower_bound(lisArr, lisArr + lis, book) - lisArr;

        lis = max(idx + 1, lis);
        lisArr[idx] = book;
    }

    cout << N - lis;
    return 0;
}

풀이

가장 긴 증가하는 부분 수열 문제입니다.
lower_bound를 활용하여 가장 긴 증가하는 부분 수열을 찾아주면 해당 수열이 가장 긴 정렬된 책의 개수입니다.
가장 긴 정렬된 책의 개수를 N개에서 빼주면 됩니다.