[백준] 책정리(1818)

문제 링크 : [백준] 책정리(1818)

문제 설명

배열이 주어졌을 때, 하나의 위치를 골라 원하는 위치로 고르는 행위를 할 수 있습니다.
이런 행위를 최소로 하여 배열을 오름차순으로 만들 때 행위의 횟수를 출력하세요.

입력

N(배열의 크기, 1 <= N <= 200,000)
A_i(배열 각각의 값, 1 <= A_i <= N)

5
2 1 4 5 3

출력

2

카테고리

#DP #LIS

시간 복잡도 상한

O(NlogN)

해결 방법

1. 한번의 움직임으로 하나의 위치는 정확한 위치에 가져다 놓을 수 있습니다.
2. 그렇다고 무턱대고 인덱스와 현재 값이 다른 수들을 세면 답이 틀립니다.
   2-1. 예시 : 2 3 1 -> 1만 맨 앞으로 움직이면 됩니다.
3. 임의의 수들간의 관계에서 역전관계(내림차순)가 있는 수들은 무조건 한번의 움직임을 가져야 합니다.
4. 반대로 말하면 역전관계가 없이 오름차순을 유지하는 수들은 움직일 필요가 없는 수들입니다.
5. 그렇다면 오름차순으로 이루어진 부분 수열들 중 가장 긴 녀석을 기준으로 다를 수들을 원래 위치로 움직이면 됩니다.
6. 즉 N-LIS의 길이를 출력하면 됩니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,d,i;
vector<int>v;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(;i<n;i++){
        cin>>d;
        if(v.empty()||v.back()<d)v.push_back(d);
        else v[lower_bound(v.begin(),v.end(),d)-v.begin()]=d;
    }
    printf("%d",n-v.size());
}