문제해설

최장증가수열(LIS)

전봇대 A와 B사이에 연결된 전깃줄 집합에서 A에 연결된 번호와 B가 연결된 번호가 둘다 오름차순이라면 전깃줄은 서로 겹치는 일이 없다. 따라서 양쪽다 오름차순으로 연결된 전깃줄의 최대 개수를 구하면된다.
양쪽다 정렬된 상태가 아니므로 A와 B의 연결상태를 저장하여 한쪽을 기준으로 먼저 정렬을 시킨다. 그 이후에 나머지 한쪽에 대해 최장증가수열(LIS) 알고리즘을 적용시키면된다.
여기서는 클래스를 생성하여 A와 B의 연결된 숫자를 저장하고 객체 배열을 만들어 A에 대해 정렬시키고 B를 탐색해가면서 LIS알고리즘을 적용시켰다. 이 문제에서 최장증가수열을 찾는 과정은 N < 100 이므로 O(N²)의 방법이 시간초과가 나지 않지만 보편적으로 O(NlogN)의 시간복잡도가 필요하므로 이분탐색 알고리즘을 적용시켰다.

DP, LIS

시간복잡도

크기가 N인 배열을 정렬하는데 NlogN, 최장증가수열을 찾는데 NlogN이므로 총 2NlogN번의 연산이 필요하다. 따라서 시간복잡도는 O(NlogN)이다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        int N, dp[], size;
        node_2565 node[];

        N = Integer.parseInt(br.readLine());
        dp = new int[N];
        node = new node_2565[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 , n2;
            n1 = Integer.parseInt(st.nextToken());
            n2 = Integer.parseInt(st.nextToken());

            node[i] = new node_2565(n1, n2);
        }
        Arrays.sort(node);

        dp[0] = node[0].B;
        size = 0;

        for (int i = 1; i < N; i++) {
            int num = node[i].B;
            if (dp[size] < num) {
                size++;
                dp[size] = num;
                continue;
            }

            int left = 0, right = size;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (dp[mid] == num) break;
                if (dp[mid] < num) {
                    if (num < dp[mid + 1]) {
                        dp[mid + 1] = num;
                        break;
                    }
                    left = mid + 1;
                }
                else {
                    if (mid == 0 || dp[mid - 1] < num) {
                        dp[mid] = num;
                        break;
                    }
                    right = mid - 1;
                }
            }
        }
        bw.write(String.valueOf(N - (size + 1)));
        bw.flush();
        bw.close();
    }
}
class node_2565 implements Comparable<node_2565>{
    int A, B;

    node_2565(int n1, int n2) {
        this.A = n1;
        this.B = n2;
    }

    @Override
    public int compareTo(node_2565 n) {
        return this.A - n.A;
    }
}