MathTrauma

문제 링크 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제에서 요구하듯이 최적의 방법으로 교차를 제거했다고 가정하자. 교차가 제거되고 남은 것을 생각한다. 문제에서 주어진 그림에서 남겨진 것을 붉은 색으로 표시했다. 교차하지 않는 남은 선들을 어떻게 기술하면 좋을까? 붉은 선의 왼쪽 번호의 대소 관계와 오른쪽 선의 대소 관계가 일치한다. 즉, 어느 한쪽을 정렬했을 때, 반대쪽은 증가 수열이다. 생각해보면 교차하지 않는다는 것은 항상 이런 뜻이..