첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.
LIS(최장 증가 부분 수열) 알고리즘과 DP를 사용
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int arr[2001];
vector<int> v;
int main() {
cin.tie(NULL); cout.tie(NULL);
ios_base::sync_with_stdio(false);
int n, num, i, maxnum = 0;
cin >> n;
for (i = 0; i < n; i++) { // 입력 받기
cin >> num;
v.push_back(num);
}
reverse(v.begin(), v.end()); // 뒤집어서 오름차순 구하는 형식으로 바꾸기
for (i = 0; i < n; i++) { // LIS
arr[i] = 1;
for (int j = 0; j < i; j++) {
if (v[j] < v[i]) {
arr[i] = max(arr[i], arr[j] + 1); // 값 업데이트
}
}
}
for (i = 0; i < n; i++) { // 최댓값
maxnum = max(maxnum, arr[i]);
}
cout << n - maxnum;
return 0;
}