2025/02/041 [백준 02565] 전깃줄 [Java] 문제https://www.acmicpc.net/problem/2565풀이유명한 LIS 문제다.우선, 전깃줄의 위치 정보를 A 또는 B를 기준으로 정렬하자.A를 기준으로 정렬해보겠다.A에서 B로 가는 전깃줄이 교차하지 않도록 최소한의 전깃줄만 제거해야 한다.교차하지 않는 전깃줄들이 최대가 되기 위해서는 A에서 B로 향하는 전깃줄들이 최대한 촘촘히 위치가 증가해야 한다.즉 B의 LIS가 교차하지 않는 전깃줄의 수와 동일하다.문제에서 요구하는 정답은 제거해야 하는 전깃줄의 수 이므로 N에서 B의 LIS를 뺀 값을 출력하자.소스코드보기 2025. 2. 4. 이전 1 다음
