문제

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

---

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다.

---

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

---

풀이

제한조건

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

접근방법

LIS, DP, 이분탐색

DP로 구하기

public int lengthOfLIS_DP(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = 1;
    int max = 1;
    
    for (int i = 1; i < nums.length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    
    return max;
}

이분탐색

public int lengthOfLIS_BS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    
    for (int num : nums) {
        int i = 0, j = size;
        while (i != j) {
            int mid = (i + j) / 2;
            if (tails[mid] < num) {
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        tails[i] = num;
        if (i == size) {
            size++;
        }
    }
    
    return size;
}

LIS를 통해 연결 시킬 수 있는 최대 개수를 구할 수 있다.
정답을 구하기 위해서는, 주어진 N에서 최대로 연결된 수를 빼면
끊어야 할 전깃줄의 수를 구할 수 있다.

일반적으로 위의 2가지 방식으로 LIS를 해결한다.
조금 더 구현량이 많고 복잡하지만, 시간적으로 유리한 이분탐색을 사용해서 풀이하였다.
비슷한 유형의 문제들이 있으니, 충분히 풀어보며 이해를 해보자.
풀다가 보면 충분히 이해가 되는 시점이 온다..

유사한 문제
1. https://www.acmicpc.net/problem/2550
2. https://www.acmicpc.net/problem/2352

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	static int N;
	static int[] arr, dp;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = stoi(in.readLine());

		arr = new int[501];
		dp = new int[501];
		for (int i = 0; i < N; ++i) {
			String[] inputs = in.readLine().split(" ");
			arr[stoi(inputs[0])] = stoi(inputs[1]);
		}

		int end = 0;
		dp[0] = arr[0];

		for (int i = 1; i < 501; ++i) {
			if (dp[end] < arr[i]) {
				dp[end + 1] = arr[i];
				end += 1;
			} else {
				int idx = search(0, end, arr[i]);
				dp[idx] = arr[i];
			}
		}
		System.out.println(N - end);
	}

	static int search(int left, int right, int target) {
		while (left < right) {
			int mid = (left + right) / 2;

			if (dp[mid] < target)
				left = mid + 1;
			else
				right = mid;
		}
		return right;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}