백준 2631 줄세우기

www.acmicpc.net/problem/2631

2631번: 줄세우기

이 문제는 전형적인 dp이면서 가장 긴 증가하는 배열을 구하면 된다. 

 

기본 예제에서 확인해보자 

 

3 7 5 2 6 1 4

 

여기서 가장 길게 증가하는 배열은 

 

3 5 6이다 이 사이의 값들만 옮겨서 1 2 3 4 5 6 7로 바꾸어주면 된다. 

 

3 5 사이로 4 

3 밑으로 1, 2

6 뒤로 7

 

이렇게 되면 1, 2, 4 ,7만 옮기면 되기 때문에 4가된다. 그래서 이 문제는 가장 길면서 증가하는 배열의 수를 구한 다음 입력 전체 크기에서 빼주면 된다. 

 

7 - 3(3, 5, 6) = 4

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int num[202], dp[202];

int main(){
	int N;
	scanf("%d", &N);

	for(int i = 0; i < N; i++){
		scanf("%d", &num[i]);
		dp[i] = 1;
	}

	for(int i = 0; i < N; i++){
		for(int j = i + 1; j < N; j++){
			if(num[i] < num[j] && dp[i] + 1 > dp[j])
				dp[j] = dp[i] + 1;
		}
	}

	printf("%d", N - *max_element(dp, dp + N)); 
}