반례를 찾기 전에, 이 코드는 무슨 로직으로 동작하는 코드이고, 왜 그렇게 하면 된다고 생각하는지 설명해 보세요.

안녕하세요.

이 코드는 입력 포트를 순회하면서 우선적으로 연결을 하고, 겹치는 상황을 3가지 경우로 나누어서 구성되었습니다.

특징은 연결 된 포트가 가장 큰 수와 그 다음으로 큰 수 2개를 prev_lo에 저장하고, 그 다음 포트의 연결 포트 번호와 관련하여 3가지 경우를 비교합니다.

1. prev_lo들 보다 클 때  : 이 경우는 겹치지 않기 때문에 바로 개수를 늘립니다(ans+=1)
2. prev_lo의 두 숫자 사이에 있을 때 : 첫번째 포트 번호보다 작으므로 더 이득입니다. 따라서 첫번째 포트에 연결된 선을 지우고, 현재 포트를 연결하여 개수를 유지합니다.
   
3. prev_lo들 의 두 숫자보다 더 작을 때 : 이 경우 한 개의 포트가 2개 이상의 포트와 겹치므로 연결하지 않는 조건으로 두었으나, 연결하지 않은 개수를 저장합니다(rej). 만약 rej의 값이 연결 된 포트 개수(ans)보다 크면 이전에 연결한 포트들을 모두 끊고 연결하지 않는 포트들로 교체하는게 이득입니다.

LIS를 사용하여 최장증가수열 로직을 사용하면 된다는 것을 검색을 통해 알아내어 O(nlogn) 복잡도로 풀 수 있다는 것을 검색을 통해 알아냈지만, 제 로직으로 O(n)까지 줄여보고 싶어서 구성했습니다.

코드에 대한 설명 없이 게시글을 올린 점 깊이 사과드립니다.

하지만 많은 고민 끝에 반례를 요청드리는 점은 진실입니다.

제가 고민한 시간보다 좀 더 고민을 많이 해보고 코드를 개선하는 모습을 가지겠습니다.

긴 글 읽어주셔서 감사합니다.

정확하게 이해는 안 됐지만, 연결하지 않은 개수를 저장하는 것만으로 그 선들끼리 교차가 없을 거라는 걸 어떻게 보장할 수 있는지는 모르겠습니다.

감사합니다!