2631번 줄세우기

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

가장 긴 증가하는 부분 수열(LIS)

https://hsdevelopment.tistory.com/224

https://algospot.com/judge/problem/read/LIS#c16488

정답 = 전체 학생 수 - 구한 값

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 202
 
int dp[Max], n;
vector<int> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d", &n);
    int input, ans = 0;
    v.push_back(0);
    for (int i = 0; i < n; i++) {
        scanf("%d", &input);
        v.push_back(input);
    }
 
    for (int i = 1; i < v.size(); i++) {        
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (v[i] > v[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        ans = max(ans, dp[i]);
    }
 
    printf("%d\n", n - ans);
 
    return 0;
}