N 층의 두 전봇대에서 N개의 선을 교차하지 않고 잇는 방법은

서로 같은 층끼리 이으면 되겠죠.

그런 경우 1-1,2-2,3-3,...N-N 이 됩니다.

왼쪽을 오름차순으로 정렬한다고 하면, 숫자가 점점 증가하는 방향이 이상적이라고 할 수 있죠.

여기서 한 선이 다른 선을 건드리게 될 때를 생각해보면, 그 선을 제외한 나머지 선 끼리는 다시 증가하는 구조를 갖게 됩니다.

결과적으로 오름차순으로 정렬된 선에서, 겹침을 유발하는 선만이 증가하는 구조를 깨뜨리게 되고, 그 외 나머지 선은 LIS로 구할 수 있죠.

@yukariko

답변 감사합니다 ! :D

이해가 잘 되네요 !