https://www.acmicpc.net/problem/2631
2631번: 줄세우기
KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기
www.acmicpc.net
LIS를 통해 이미 정렬된 애들은 빼고 나머지 애들만 정렬하는 코드를 사용했다.
LIS짤 때마다 동적 테이블 1로 초기화하는걸 안해서 시간이 오래걸린다.
웰논 알고리즘들을 언제 한번 정형화해서 외우든지 해야겠다.
물론 원리를 외우는게 맞긴 한데 문제 풀 때는 그냥 외워서 쓰는게 나을거같다. 문제 풀 때마다 원리 생각해서 짜면 너무 느림..
더보기
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
vector<int> arr, dp;
cin >> n;
arr.resize(n + 1);
dp.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
dp[i] = 1;
}
int mx = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j]) {
if (dp[i] < dp[j] + 1) dp[i] = dp[j] + 1;
if (mx < dp[i]) mx = dp[i];
}
}
}
/*for (int i = 1; i <= n; i++) {
cout << dp[i] << " ";
}
cout << "\n";*/
cout << n - mx << endl;
return 0;
}