[BOJ 2565] 전깃줄 (Java)

문제

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

2565번: 전깃줄

BOJ 2565 전깃줄

풀이

전체 전깃줄 개수 - 전깃줄의 최장증가 수열 개수

= 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수

 

A 값의 순서로 B 값을 수열로 만들어보면 {8, 2, 9, 1, 4, 6, 7, 10} 이다. 이 수열의 최장증가수열의 개수를 구해서, 전체 전깃줄 개수에서 빼면 답을 구할 수 있다.입력이 정렬되어 들어오지 않기 때문에 A값 기준으로 정렬한 후, 이분 탐색 이용하여 LIS의 개수를 구한다. 

 

LIS 알고리즘 참고

2021.11.04 - [Algorithm] - [Algorithm] LIS 알고리즘 (최장증가수열 알고리즘)

[Algorithm] LIS 알고리즘 (최장증가수열 알고리즘)

 

소스코드

package lis;

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

public class BOJ2565 {

    public static int[][] arr;
    public static int[] temp;
    public static int N;
    public static void main(String[] args) throws Throwable {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][2];
        temp = new int[N];
        StringTokenizer st = null;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                return o1[0] - o2[0];
            }
        });

        int idx = 0;
        temp[idx] = arr[idx][1];
        for(int i = 1; i < N; i++){
            if(temp[idx] < arr[i][1]){
                idx++;
                temp[idx] = arr[i][1];
                continue;
            }
            temp[lowerbound(0, idx, arr[i][1])] = arr[i][1];
        }

        System.out.println(N - (idx + 1)); //idx 0부터 데이터가 있으므로
    }

    public static int lowerbound(int L, int R, int num){
        // temp배열에서 num의 lowerbound를 찾아서 index를 리턴
        int mid = 0;
        while(L < R){
            mid = (L+R)/2;
            if(num <= temp[mid]) R = mid;
            else L = mid+1;
        }
        return R;
    }
}