[BOJ 2631] 줄 세우기

- 문제 요약

 

N명의 아이들이 임의의 순서로 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

옮겨지는 아이의 수를 최소로 하기 위해서는 현재 서 있는 줄에서 LIS를 찾고, 전체 어린이 수에서 LIS의 길이를 빼주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 201
int n,arr[MAX],dp[MAX],mx;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	for(int i=0;i<n;i++){
		dp[i]=1;
		for(int j=0;j<i;j++){
			if(arr[i]>arr[j] && dp[i]<dp[j]+1){
				dp[i]++;
			}
		}
		if(mx<dp[i]){
			mx=dp[i];
		}
	}
	cout<<n-mx;
}

코드 제출 결과