[백준] 18353 병사 배치하기 [자바]

 

 

---

https://st-lab.tistory.com/137

[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class Main {
	static long ans = 0;
	static int[] arr;
	static int[] dp;
 	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		arr = new int[N];
		dp = new int[N];
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int re = 0;
		for(int i = 0; i < N; i++) {
			re = Math.max(re, LIS(i));
		}
		System.out.println(N-re);
 	}
 	static int LIS(int N) {
 		if(dp[N] == 0) {
 			dp[N] = 1;
 			
 			for(int i = N-1; i >= 0; i--) {
 				if(arr[N] < arr[i]) {
 					dp[N] = Math.max(dp[N], LIS(i) + 1);
 				}
 			}
 		}
 		return dp[N];
 	}
}