[백준 02565] 전깃줄 [Java]

문제

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

---

풀이

유명한 LIS 문제다.

우선, 전깃줄의 위치 정보를 A 또는 B를 기준으로 정렬하자.

A를 기준으로 정렬해보겠다.

A에서 B로 가는 전깃줄이 교차하지 않도록 최소한의 전깃줄만 제거해야 한다.

교차하지 않는 전깃줄들이 최대가 되기 위해서는 A에서 B로 향하는 전깃줄들이 최대한 촘촘히 위치가 증가해야 한다.

즉 B의 LIS가 교차하지 않는 전깃줄의 수와 동일하다.

문제에서 요구하는 정답은 제거해야 하는 전깃줄의 수 이므로 N에서 B의 LIS를 뺀 값을 출력하자.

---

소스코드

보기