[백준OJ] 1365번 꼬인 전깃줄

https://www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

---

 

 

풀이

말을 살짝 바꿔서 잘라야되는 전깃줄을 구하는것이아닌, 자르지 않아도되는 전깃줄의 최대값을 구해준다고 생각을 하면 쉽게된다. 

그럼 여기서 자르지않아도 되는 전깃줄의 최대값은 어떻게 구해줄까? 방법은 바로 증가하는 수열의 최대길이를 구해주면된다.

이를 위해 Lower_bound함수를 구현해준 뒤, 자르지않아도 되는 전깃줄의 최대값을 구해주어 N에서 빼주면 답이 나온다.

시간복잡도

Lower_bound의 시간은 O(logN)이 되는데, 이를 N번 반복하기때문에 O(NlogN)이 된다.

 

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> v=new ArrayList<>();
    static int n;

    static int lower_bound(int num){
        int l=0;
        int r=v.size();

        while(l<r){
            int middle=(l+r)>>1;

            if(v.get(middle)>=num){
                r=middle;
            }
            else{
                l=middle+1;
            }
        }

        return l;
    }

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=0;i<n;i++){
            int line=scanner.nextInt();
            int ind=lower_bound(line);
            if(ind>=v.size()){
                v.add(line);
            }
            else{
                v.set(ind,line);
            }
        }
        System.out.println(n-v.size());
        scanner.close();
    }
}