boj 2631: 줄세우기

주어진 예시를 보면 줄 세우기 과정은 아래와 같다.

3 7 5 2 6 1 4

3 7 4 5 2 6 1

3 4 5 2 6 1 7

1 3 4 5 2 6 7

 

즉, 제자리에 있는 아이들의 번호는 아래와 같다. == LIS

3 7 5 2 6 1 4

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		int child[] = new int[n + 1];
		int ans[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			child[i] = in.nextInt();
		}
		ans[1] = 1;

		for (int i = 2; i <= n; i++) {
			int max = 0;
			for (int j = 0; j < i; j++) {
				if (child[i] > child[j]) {
					max = Math.max(max, ans[j]);
				}
			}
			ans[i] = max + 1;
		}

		Arrays.sort(ans);
		System.out.println(n - ans[n]);
	}
}