[백준 2631] 줄세우기

 

가장 적은 횟수로 순서대로 세우려면

전체 아이의 수 - (가장 큰 증가 수열의 길이) 를 하면된다.

 

가장 큰 증가 수열의 길이를 구하는 법은 여기에 있다.

 

 

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int c[] = new int[n];
        int dp[] = new int[n];
        
        for(int i=0; i<n; i++)
            c[i] = sc.nextInt();
        
        int max = 0;
        for(int i=0; i<n; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(c[i] > c[j] && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
                if(max < dp[i])
                    max = dp[i];
            }
        }
        
        System.out.println(n - max);
        sc.close();
}