[LIS] BOJ 2631 줄세우기

문제 링크 : www.acmicpc.net/problem/2631

2631번: 줄세우기

문제에서 한 아이의 위치를 옮기는 것은 항상 맨 앞으로 보내거나, 맨 뒤로 보내는 것에 유의하자.

이렇게 위치를 옮기는 횟수를 최소화하려면, 최초 아이들의 순서에서 이미 번호 순으로 서 있는 아이들을 제외한 나머지를 옮기면 된다.

즉, 예제의 (3 7 5 2 6 1 4) 에서, 이미 3, 5, 6의 올바른 순서가 존재하므로 이들을 제외한 나머지 7, 2, 1, 4를 옮기면 1 ~ 7의 오름차순 순서를 만들 수 있다. (옮기는 순서는 고려하지 않아도 된다.)

따라서 이 문제는 주어진 수열에서 LIS를 찾는 문제임을 알 수 있다.

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n;
int arr[201], dp[201];
 
void lis() {
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if(arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}
 
void init() {
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        dp[i] = 1;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    lis();
 
    int max_dp = 0;
    for (int i = 1; i <= n; i++) max_dp = max(max_dp, dp[i]);
    printf("%d\n", n - max_dp);
 
    //system("PAUSE");
    return 0;
}