[Java] 백준 2568 (전깃줄 - 2) Gold 1

Problem : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net Approach 겉으로는 그렇게 보이지 않을지도 모르지만 LIS (Longest Increase Subsequence) 문제이다. 한 쪽 전봇대를 오름차순으로 정렬한 뒤, 최대 LIS의 요소가 아닌 전깃줄들을 제거하면 된다. LIS 는 시간제한에 따라(입력데이터의 범위에 따라) DP 혹은 이분탐색으로 풀이가 가능한데, 여기서는 이분탐색으로 풀이를 해야한다. 이분 탐색을 이용하..