[2631] 줄세우기

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

2631번: 줄세우기

<문제>

O(N^2)이든 O(NlogN)이든 LIS의 길이를 구하고, N-LIS의 길이를 출력하면 된다.

 

이미 오름차순을 유지하고 있는 아이를 움직일 필요는 없으므로,

또한 움직일 필요가 없는 아이를 최대화해야 옮기는 아이의 수를 최소화할 수 있으므로

문제의 최적해를 LIS로부터 찾을 수 있다.

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, a[201], dp[201];
int main(void) {
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i] = 1;
    }
    int ans = 0;
    for (i = 1; i <= n - 1; i++) {
        for (j = i + 1; j <= n; j++) {
            if (a[i] < a[j]) {
                dp[j] = max(dp[i] + 1, dp[j]);
                ans = max(dp[j], ans);
            }
        }
    }
    cout << n - ans;
    return 0;
}