[백준] 2565번 : 전깃줄 - JAVA [자바]

링크

전깃줄이 교차하는 경우를 제거하기 위해 전깃줄을 없애 전길줄이 교차하지 않도록 만든다.

전깃줄의 개수는 100 이하의 자연수, 위치의 번호는 500 이하의 자연수, 같은 위치에 여러 개의 전깃줄이 연결될 수 없다.

전깃줄을 없애는 최소 개수를 구하라.

Idea

전깃줄을 없애는 최소 개수는 전깃줄을 교차하지 않도록 만들기 위해 남겨야 하는 전깃줄의 최대 개수이다.

전깃줄이 교차하지 않는다는 것의 의미는 무엇일까?

전깃줄의 왼쪽 전봇대에서의 번호가 증가하는 순서대로, 오른쪽 전봇대에서의 번호도 증가한다는 것이다.

입력으로 들어오는 전선들을 왼쪽 전봇대에서의 번호 순으로 정렬해보자.

교차하지 않는 전선 몇개를 골랐을 때 대응되는 오른쪽 전봇대에서의 번호는 증가하는 순서가 된다.

따라서 이 문제는 최장 증가 부분수열 문제로 환원된다.

Code

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        // 왼쪽 전봇대에서의 번호 순으로 정렬
        Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));

        int[] dp = new int[n];
        int max = 0;

        // 최장 증가 부분수열 찾기
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i][1] > arr[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

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

시간 복잡도는 $O(n^2)$이다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        // 왼쪽 전봇대에서의 번호 순으로 정렬
        Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));

        int[] dp = new int[n];
        int length = 0;

        // 최장 증가 부분수열 찾기
        for (int i = 0; i < n; i++) {
            int pos = Arrays.binarySearch(dp, 0, length, arr[i][1]);
            if (pos < 0) {
                pos = -pos - 1;
            }
            dp[pos] = arr[i][1];
            if (pos == length) {
                length++;
            }
        }

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

이분 탐색을 이용한 풀이이다. 시간 복잡도는 $O(nlogn)$이다.

Result

입력

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

에 대하여 전봇대에 연결된 전선들을 왼쪽 전봇대에서의 번호 순으로 정렬하면 다음과 같다.

[1,   8]
[2,   2]
[3,   9]
[4,   1]
[6,   4]
[7,   6]
[9,   7]
[10, 10]

맨 아래 4부터 10까지의 전선들이 최장 증가 부분수열이다.

즉 정답은, 8 - 5의 3이 되고, 제출 결과 통과하는 것을 알 수 있다.

최장 증가 부분수열

3 4 1 4 7 2 5 8 6

위와 같은 수열이 있다고 가정해보자

마지막 원소로 5를 붙인다고 하면 다음과 같은 조건을 만족하는 가장 긴 부분수열을 찾으면 된다.

• 5보다 앞에 있다.
• 5보다 작은 수로 끝난다.

이를 기반으로, dp[i]를 다음과 같이 정의한다.

마지막으로 뽑은 수가 $a_i$ 일 때 가장 긴 증가하는 부분수열의 길이

작은 문제와 큰 문제의 관계

지금까지의 증가수열에 $a_i$를 붙이기 위해서는

(지금까지의 증가수열의 index가 j 라고 한다면) $j < i$를 만족하고 마지막 수 $a_j$는 $a_i$보다 작아야 한다.

$dp[i] = max(dp[j] + 1)$

가 됨을 알 수 있다.