백준[2631] 줄세우기

문제 설명

문제 링크

http://icpc.me/2631

2631번: 줄세우기

풀이

LIS(Longest Increasing Subsequence)를 이용하여 풀 수 있다.

가장 긴 증가하는 부분 집합을 구하고, 그 부분 집합에 속하지 않는 사람들만 이동하면 되기 때문에 n - LIS를 하면 된다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[202], dp[202];
int ret = 0;

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