[백준] 2565: 전깃줄 - JAVA

16 Jul 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

A와 B기둥에 전깃줄을 연결하는데 서로 겹치는 전깃줄이 없어야 한다.

입력을 받아 A기준으로 오름차순으로 정렬한다.

예제에서 정렬하면 A는 오름차순으로 정렬되고 B는 다음과 같이 된다.

{8, 2, 9, 1, 4, 6, 7, 10}

전깃줄을 교차되지 않게 하기 위해 없애야 하는 최소의 개수를 구해야 한다.

즉, 가장 많이 연결이 되어야 한다는 의미이다.

정렬을 하니 주어진 배열에서 가장 긴 증가하는 부분수열(LIS)의 길이를 찾는 문제로 바뀌었다.

LIS의 길이를 찾아 N에서 빼주면 없애야 할 전깃줄의 개수가 나온다.

LIS를 찾는 방법은 DP를 이용한 방법과 이분 탐색을 이용한 방법이 있다.

DP를 이용한 방법은 들어갈 수 있는 인덱스를 배열에 기록하면서 자신보다 전을 탐색해서 찾는 방법이다.

이분 탐색을 이용한 방법은 새로운 배열에 들어갈 값을 그대로 넣는데 들어갈 수 있는 위치를 이분 탐색을 통해 찾고, 배열이 채워진 길이가 LIS의 길이가 되는 방법이다.

이 문제는 케이스가 크지 않아 시간이 DP가 빠르게 나왔다. 큰 크기에서는 통상적으로 이분 탐색이 빠르다.

---

DP

메모리: 14116KB

시간: 124ms

언어: Java 11

코드

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];
        StringTokenizer st;
        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[] 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[j][1] < arr[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            max = Math.max(max, dp[i]);
        }

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

}

---

이분 탐색

메모리: 14192KB

시간: 128ms

언어: Java 11

코드

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

public class Main {
    static int[] dp;

    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];
        StringTokenizer st;
        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];
            }
        });

        dp = new int[N + 1];
        int max = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i][1] > dp[max]) {
                max++;
                dp[max] = arr[i][1];
            } else {
                int idx = binarySearch(0, max, arr[i][1]);
                dp[idx] = arr[i][1];
            }
        }

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

    private static int binarySearch(int left, int right, int key) {
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (dp[mid] < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

}