boj 2565 정답

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. Logic - 기본적인 LIS문제이다. 이 문제가 LIS인 이유는 전깃줄이 교차하지 않아야한다는 것은 이전 전깃줄의 번호가 다음 전깃줄의 번호보다 커지면 안되고 항상 작은 번호여야하기 때문에 증가하는 부분수열이 될 수 밖에 없다. 다른 LIS문제와 다른점은 단지 입력 값을 pair로 받아 준 다음 A를 기준으로 오름차순 정리해주고 B를 기준으로 LIS를 찾아주면 된다. 공부겸 시간복잡도가 O(nlo..