대엉코딩

www.acmicpc.net/problem/7570

1. 풀이방법

 - 몇가지 예시를 직접 종이에 써서 알아보고, 코드로도 짜보고 하면서 알아낸 것이

 - 순방향(? 증가하는) 쪽의 가장 긴 증가수열의 길이를 알아내는 것이 핵심 이었습니다.

 - 근데 한번의 작업으로 맨 앞 혹은 맨 뒤 양 끝으로만 보낼 수 있기 때문에 그냥 최장증가수열이 아닌 !

 - 1씩 증가하는 최장증가수열의 길이를 구해야 했습니다!!!!

 - 입력의 범위를 보니 이중반복문이 들어갈 경우 시간초과가 명백하여서 dp를 통해서 입력을 받으면서 구했습니다.

2. 주의사항 

 - 지금보면 단순해보이는 numarr[tmp]=numarr[tmp-1]+1 이 것을 생각해내는 게 꽤 어려웠습니다 ㅠㅠㅠ

 - dp에 익숙하지 않아서 일까요...꽤 오래걸렸습니다...

 - 보시는 분들 중에 이해가 안되는 분들은 임의의 길이 7 정도의 입력을 직접 그려보면서 써가면서 하시면 

 - 이해가 잘 되실 것 같습니다.

3. 나의코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int N;
int numarr[1000001];
int maxlistcount;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp; 
		numarr[tmp] = numarr[tmp - 1] + 1;
		maxlistcount = max(maxlistcount, numarr[tmp]);
	}
	cout << N - maxlistcount << "\n";
	return 0;
}