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

문제

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

풀이

DP를 이용하여 풀었다.
DP 중에서도 가장 긴 오름차순 길이를 응용하였다.
예를 들어서 예제에서 다음과 같이 배열되어있을 때

3 7 5 2 6 1 4

다음 배열에서 가장 긴 오름차순의 길이는 3이다.
그러면 가장 긴 오름차순의 길이에 포함되지 않은 나머지 숫자들의 자리만 바꿔주면 된다.
즉, 다음과 같이 식을 세우면 된다.

N(전체 번호의 개수) - 가장 긴 오름차순의 길이

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String args[]) throws IOException {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] input = new int[N];
        for(int i=0;i<N;i++) input[i] = scan.nextInt();

        int[] dp = new int[N];
        dp[0] = 1;

        int ans = 0;
        for(int i=1;i<N;i++){
            dp[i] = 1;
            for(int j=0;j<i;j++){
                if(input[i]>input[j]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(N-ans);

    }
}