백준 18353번 병사 배치하기 JAVA

어렵진 않은 문제였다. 가장 긴 증가 수열을 찾고 최대 증가 수열에 포함되지 않는 숫자를 구하면 됨으로

어렵진 않은 문제였다. 가장 긴 증가 수열을 찾고 최대 증가 수열에 포함되지 않는 숫자를 구하면 됨으로

"배열의 길이 - 가장 긴 증가 수열" 을 하면 답이 나온다. 점점 DP에 감을 잡아가는건가..

import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.function.ToIntFunction;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] soldiers =new int[N];
        int[] dp = new int[N+1];

        Arrays.fill(dp,1);
        String temp = br.readLine();
        StringTokenizer st = new StringTokenizer(temp);
        int k = 0;
        while (st.hasMoreTokens()){
            soldiers[k++]=Integer.parseInt(st.nextToken());
        }

        for(int i=1;i<N;i++){
            for(int j=0;j<=i;j++){
                if(soldiers[i]<soldiers[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int max = 0;
        Arrays.sort(dp);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(N-dp[N]));
        bw.flush();
        bw.close();
    }
}