1365 꼬인 전깃줄

 

 

이 문제는 가장 긴 증가하는 부분 수열 문제와 풀이법이 같다.

 

참고 :

https://happy-fun.tistory.com/207

12015 가장 긴 증가하는 부분 수열 2

 

그래서 이 방법으로 문제를 풀면 된다.

 

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

public class Main {
	
    public static void main(String[] args)  throws IOException {
  
    	
    	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           StringTokenizer st = new StringTokenizer(br.readLine(), " ");
       	   int N = Integer.parseInt(st.nextToken());
           
       	   int input[] = new int[N];
		
       	   st = new StringTokenizer(br.readLine(), " ");
		   for(int i=0; i<N; i++) {
				input[i] = Integer.parseInt(st.nextToken());
		    }
			
			
		   ArrayList<Integer> list = new ArrayList<>();
		   list.add(0);
			
		   for(int i=0; i<N; i++) {
		   int value = input[i];
				
		   if(list.get(list.size()-1) < value) {
					
					list.add(value);					
					
			}else {
					
				
				int left = 1;
				int right = list.size()-1;
					
				while(left<right) {
					int mid = (left+right)/2;
					
					if(list.get(mid)<value) {
						left = mid +1;
					}else {
						right = mid;
					}
				 }
					
					list.set(right, value);
			 }
			}
			
			
			System.out.println(N-(list.size()-1));
    }
}