2565 - 전깃줄

문제: boj.kr/2565
날짜: 09/11 (수)
성공여부: X [00:52:17]

 

 

전깃줄이 교차하지 않도록 최소의 전깃줄을 제거하고 그 개수를 출력하는 문제이다. 가장 먼저 생각해볼 수 있는 알고리즘은 완전탐색이다. 모든 전깃줄을 1개, 2개, 3개, ..., n개까지 제거하면서 최소의 개수를 구하는 것이다. 전깃줄의 개수가 최대 100개이니까 이 방법은 전깃줄을 고르는데에만 100C1 + 100C2 + 100C3 + ... + 100C100만큼의 시간이 걸린다. 가장 큰 경우의 수인 100C50가 약 1 * 10^29이므로 이 방법은 안된다.

 

그럼 교차하는 수가 많은 전깃줄 위주로 없애는 방법을 생각할 수 있다. 위의 예제를 가장 많은 전깃줄을 교차하는 순으로 정렬하면,

 

1 8

3 9

4 1

...

 

이러면 0개인 전깃줄이 m이라고 했을 때, 교차하는 전깃줄을 선택하는 것만해도 n-mC1 + n-mC2 + ... + n-mCn-m 으로 볼 수 있다. 이것도 결국 위의 완탐과 다를바 없어진다. 아예 생각을 뒤집어 전깃줄을 교차하지 않고 최대로 연결하는 전깃줄 개수를 찾아 전체 전깃줄 개수에서 빼면 답이지 않을까?

 

그림을 기준으로 교차하지 않는 모든 경우의 수는 각각 아래와 같다.

 

(1, 8), (3, 9), (10, 10)

(2, 2), (6, 4), (7, 6), (9, 7), (10, 10)

(4, 1), (6, 4), (7, 6), (9, 7), (10, 10)

 

이 경우의 수들을 모두 살펴보면 정렬된 A를 기준으로 B가 오름차순을 유지하고 있다. 즉, 각각의 경우의 수가 증가하는 부분 수열임을 알 수 있다. 근데 우리가 찾고자 하는건 교차하지 않고 최대로 연결하는 경우의 수이므로 결국 이 문제는 정렬된 A를 기준으로 B가 LIS인 길이를 구하면 되는 것이다!

 

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
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;
        int n = Integer.parseInt(br.readLine());

        int[][] cable = new int[n][2];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            cable[i][0] = Integer.parseInt(st.nextToken());
            cable[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(cable, (Comparator.comparingInt(o -> o[0])));

        int[] lis = new int[n];
        lis[0] = cable[0][1];
        int idx = 0;
        for (int i = 1; i < n; i++) {
            if (cable[i][1] > lis[idx]) lis[++idx] = cable[i][1];
            else {
                int low = -1;
                int high = idx;

                while (low + 1 < high) {
                    int mid = (low + high) / 2;

                    if (lis[mid] >= cable[i][1]) high = mid;
                    else low = mid;
                }

                lis[high] = cable[i][1];
            }
        }

        int ret = 0;
        for (int i = 0; i < n; i++) if (lis[i] != 0) ret++;

        System.out.println(n - ret);
    }
}