[7570] 줄 세우기

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

7570번: 줄 세우기

<문제>

단순 nlogn LIS인줄 알았는데, {1 3 4 2} 에서 한번에 {1 2 3 4}를 만들 방법이 없다.

{1 3 4 2} -> {2 1 3 4} -> {1 2 3 4}처럼, 두번에 걸쳐서 이동해야 한다.

연속하는 수로 이루어진 LIS를 찾아주면 되겠다.

어디든 끼워넣을 수 있는 "[2631] 줄세우기" 문제와 연계하여 곱씹어볼만한 문제다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, cnt, a[1000005], dp[1000005];
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int i;
    for (i = 0; i < n; i++) {
        int x;
        cin >> x;
        dp[x] = dp[x - 1] + 1;
        cnt = max(dp[x], cnt);
    }
    cout << n - cnt;
    return 0;
}