[알고리즘] 백준 - 2565 ( 전깃줄 ) / 자바

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

class Solution {
	static int N;
	static int max;
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());// 전깃줄 갯수
		int[] arr = new int[501]; // 
		int[] dp = new int[501];
		
		//전깃줄이 하나일 경우 0을 출력
		if(N == 1) {
			System.out.print(0);
			return ;
		}
		
		max  =0 ;  // max는 index의 최댓값 ( 전깃줄이 N개지만 인덱스가 N보다 큰 경우를 위해 )
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			arr[start] = end;
			max = max >  start ? max : start;
			}
		
		
		LIS(arr , dp); //가장 큰 증가하는 수열 구함
		
		//최장 길이 를 구함
		int maxDp = 0;
		for (int i = 1 ; i <= max ; i++) {
			maxDp = maxDp > dp[i] ? maxDp : dp[i];
		}

		//연결가능한 포트  - 전깃줄이 없는 포트의 갯수 - 최장길이 수열의 길이
		System.out.println(max - (max-N) - maxDp);
		
	}	
	
	//최장길이 수열 구함
	static void LIS(int[] arr , int[] dp) {
		int maxIndex;
		int maxValue;
		for (int i = 1; i <= max; i++) {
			if (arr[i] == arr[i - 1]) {
				dp[i] = dp[i - 1];
			}else if(arr[i] == 0){
				continue;
			}else {		
				maxIndex = -1;
				maxValue = 1;
				for (int j = i - 1; j >= 0; j--) {
					//현재 값보다 작고 길이가 긴 인덱스를 찾음
					if (arr[j] < arr[i] && maxValue <= dp[j]) {
						maxValue = dp[j];
						maxIndex = j;
					}
				}
				// 자신보다 작은 값이 없으면 1을 , 있으면 가장 큰 길이를 가지는 값에 +1
				dp[i] = maxIndex == -1 ? 1 : dp[maxIndex] + 1;
			}
		}	
	}
}