[ 백준 BOJ ]1818번 - 책정리 (C++)

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

생각 흐름

• 핵심은 증가하는 가장 긴 배열을 그대로 두고 나머지를 옮겨주면 된다.
• 예를 들어 1 3 4 7 6 2 일 때 1 3 4 6 이 증가하는 가장 긴 배열이다.
• 이로 인해 정답은 N - 증가하는 가장 긴 배열의 크기를 넣으면 된다.

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

using namespace std;

int N;
vector<int> input;
int dp[250000];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int answer = 0;
    
    cin>>N;
    for(int i = 0; i<N; i++){
        int tmp;
        cin>>tmp;
        
        input.push_back(tmp);
    }
    
    dp[0]=-987654321;
    for(int i = 1; i<=N; i++){
        dp[i]=987654321;
    }
    
    for(int i = 0; i<N; i++){
        auto a = lower_bound(dp, dp+(N+1), input[i]) - dp;
        
        dp[a] = input[i];
        answer = max(answer, (int)a);
    }
    
    cout<<(N-answer)<<endl;
    
    return 0;
}