chatterboy   1년 전

안녕하세요.

이 문제가 lis로 해결할 수 있더군요. 하지만 제가 아무리 예제 데이터를 만지작거려도 어떻게 lis로 해결이 되는지

이해가 안되네요. ㅠ

yukariko   1년 전

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

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

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

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

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

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

chatterboy   1년 전

yukariko

답변 감사합니다 ! :D

이해가 잘 되네요 !

댓글을 작성하려면 로그인해야 합니다.