[BOJ] 2631번 : 줄세우기(C++)

문제 링크 : 백준 2631번

[문제 접근]

LIS를 찾아서 그 수열을 제외한 나머지를 옮겨주면 된다.
따라서 LIS를 찾고 전체 n개에서 빼면 정답이다.

[소스 코드]

#include <iostream>
#include <algorithm>

using namespace std;
int n;
int dp[201];
int arr[201];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=0 ; i<n ; i++) {
        cin >> arr[i];
    }
    int ans=0;
    dp[0] = 1;
    for(int i=1 ; i<n ; i++) {
        int now = 0;
        for(int j=0 ; j<i ; j++) {
            if(arr[i]>arr[j]) {
                now = max(now, dp[j]);
            }
        }
        dp[i] = now+1;
        ans = max(ans, dp[i]);
    }
    cout << n-ans;
    return 0;
}