[백준 18353 JAVA] 병사 배치하기

 

기본적인 증가하는 가장 긴 수열 문제

 

조건이 맞을 때, 앞에서 계산한 것 중 가장 큰 것을 가져와 +1해주면 되는 문제이다.

 

이 문제에서는 증가가 아닌 감소하는 수열을 구하면 된다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arr[] = new int[N];
        int dp[] = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if(arr[i]<arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        System.out.println( N- Arrays.stream(dp).max().getAsInt());
    }
}