교차로 잇기

도로 하나는 서로 다른 두 교차로를 사용하므로, 만들 수 있는 도로의 개수는 항상 $\left\lfloor \frac{N}{2} \right\rfloor$개 이하이다.

이제 이 개수를 항상 만들 수 있음을 보이면 된다. 모든 교차로를 $x$좌표가 증가하는 순서로 정렬하고, 앞에서부터 두 개씩 묶어 $(1,2),(3,4),\ldots$에 해당하는 교차로 쌍을 연결하자. 서로 다른 두 도로가 사용하는 $x$좌표 구간은 서로 겹치지 않는다. 따라서 두 도로는 중간에서 교차하지 않는다. 또한 각 교차로는 최대 한 번만 사용된다.

그러므로 정답은 $\left\lfloor \frac{N}{2} \right\rfloor$이다. 실제 프로그램은 좌표를 모두 입력받은 뒤 $\lfloor N/2 \rfloor$만 출력하면 된다.

시간 복잡도는 $O(N)$이고, 메모리 복잡도는 $O(1)$이다.

Solution written by GPT5.5