백준 2631번 줄세우기

백준 2631번 줄세우기

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include <algorithm>
#include<set>
#include<map>
using namespace std;
 
int n;
int cache[1001];
int S[1001];
int lis(int start) {
 
    int& ret = cache[start + 1];
    if (ret != -1) return ret;
    
    ret = 1;
    for (int next = start + 1; next < n; next++)
        if (start == -1 || S[start] < S[next])
            ret = max(ret, 1 + lis(next));
 
    return ret;
}
 
int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    memset(cache, -1, sizeof(cache));
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> S[i];
    
    cout << n-(lis(-1) - 1) << endl;
 
 
    return 0;
}
 
 

문제 출처:https://www.acmicpc.net/problem/2631

가장 긴 증가수열을 찾아서 전체에서 수열크기를 빼주면 정답이된다.