BOJ 7570번 줄 세우기

BOJ : https://www.acmicpc.net/problem/7570

github : https://github.com/junho0956/Algorithm/blob/master/7570/7570/%EC%86%8C%EC%8A%A4.cpp

 

무작위로 위치시킬 수 있는 경우는 가장 긴 증가수열을 뺀 값으로 해결할 수 있지만

맨 앞이나 뒤로 위치시켜야 하는 경우는 lis로 해결할 수 없습니다.

1씩 연속적으로 증가하는 가장 긴 증가수열을 제외한 값들을 이동시켜야 합니다.

 

// 1씩 증가하는 lis 를 구한다.
// 5 2 4 1 3
/*
0 0 0 0 0
0 0 0 0 1
0 1 0 0 1
0 1 0 1 1
1 1 0 1 1
1 1 2 1 1
*/
 
#include <iostream>
using namespace std;
 
int dp[1000001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N; cin >> N;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int n; cin >> n;
        dp[n] = dp[n - 1] + 1;
        ans = ans < dp[n] ? dp[n] : ans;
    }
    cout << N - ans;
    return 0;
}