[백준 2631] 줄세우기 (JAVA)

https://www.acmicpc.net/problem/2631

2631번: 줄세우기

 

 

LIS 증가하는 수열의 최대 갯수를 찾아서

n -  LIS 하면 옮겨야 하는 최소값이 나온다 !

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		
		int max=0;
		int[] dp = new int[n];
		dp[0]=1;
		for(int i=1;i<n;i++) {
			dp[i]=1;
			for(int j=0;j<i;j++) {
				if(arr[j]<arr[i]) {
					dp[i]=Math.max(dp[i],dp[j]+1);
				}
			}
			max= Math.max(max, dp[i]);
		}
		
		System.out.println(n-max);
		
	}

}