[백준][BOJ2565] 전깃줄

1. 문제 : https://www.acmicpc.net/problem/2565

2565번: 전깃줄

---

2. 풀이 : Binary Search

---

3. 설명

그림[1]

그림[1]과 같이 3개의 전깃줄을 제거하였을 때, 남아있는 모든 전깃줄이 교차하지 않음을 확인할 수 있다. 

전봇대A를 기준으로 위치 1부터 10까지 차례대로 전깃줄을 연결하였을 때, 연결되는 전봇대 B의 위치 순서는 그림[2]와 같으며, 교차하지 않는 전깃줄은 최대 증가수열임을 알 수 있다.

그림[2]

마찬가지로, 전봇대 B를 기준으로 위치 1부터 10까지 차례대로 연결되는 전봇대 A의 위치 순서는 그림[3]과 같으며, 교차하지 않는 전깃줄은 최대 증가수열임을 알 수 있다.

그림[3]

따라서, A 또는 B 전봇대를 기준으로 잡았을 때 얻을 수 있는 최대 증가수열의 개수를 모든 전깃줄 수에서 뺀 나머지가 최소로 제거해야 할 전깃줄 수이다.

---

4. 코드