[백준] 줄세우기(2631)

참고: www.acmicpc.net/problem/2631

2631번: 줄세우기

 

- dp 문제

- LIS 를 잘 이용해야 함

- 정렬이 필요한 숫자의 최소 수 : 증가 수열의 값이 최대가 되는 값의 갯수 => LIS가 필요함

 

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int max = 0;
        int[] C = new int[N];
        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            C[i] = sc.nextInt();
        }

        dp[0] = 1;

        for (int i = 1; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                // c[0] 부터 올라가면서 확인
                if(C[i] > C[j] && dp[i] < dp[j] + 1) {
                    // 증가
                    dp[i] = dp[j] + 1;
                }
            }
            max = Math.max(max, dp[i]);
        }

        System.out.println(N-max);
    }
}