[BOJ/백준][Gold2] 1818 : 책정리 (C++)

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

1818번: 책정리

 

 

[난이도] Gold2
[유형] DP

[풀이]
오름차순으로 되어있는 최대 길이 수열을 구한 뒤 이 값을 N에서 빼주면 됩니다.
이게 가능한 이유는
오름차순으로 되어있는 수들은 건드릴 필요가 없고,
오름차순으로 되어있지 않은 나머지 수들은 최소 한번씩은 움직여야 하기 때문입니다.

 

오름차순으로 되어있는 최대 길이 수열은 결국 유명한 증가하는 최대 부분 수열(LIS) 입니다.

이것은 DP로 구할 수 있습니다. N이 20만이기 때문에 O(NlogN) 알고리즘을 사용해서 구해주면 됩니다. 

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,a[200000];
vector<int> v;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    v.push_back(a[0]);
    for(int i=1;i<N;i++){
        auto idx = lower_bound(v.begin(),v.end(),a[i])-v.begin();
        if(idx<v.size()) v[idx]=a[i];
        else v.push_back(a[i]);
    }
    printf("%d",N-v.size());
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/1818.cpp