소는 왜 길을 건너갔을까? 11 timer 2s memory 512MB

존은 1번부터 N번까지 번호가 붙여진 N쌍의 소를 총 2N마리 키우는데, 어떤 쌍의 소들은 다른 소들과의 사이보다 더 친밀하기도 하다. 오랜 관찰 끝에 존은 소의 번호가 a인 소와 b인 소의 경우 |a - b| \leq 4 인 경우 더 친밀하다는 사실을 알아냈다.

각 소는 N개의 서로 다른 목초지에서 살고 있다. 각 목초지는 북쪽에서 남쪽으로 이어지는 하나의 긴 도로를 중심으로 서쪽과 동쪽으로 나뉘어져 도로를 따라 일렬로 나란히 붙어있다.

친밀한 관계의 소들끼리는 자주 왕래가 이루어져야 스트레스를 받지 않게 되기에 존은 도로에 횡단보도를 설치하여 친밀한 소들이 사는 목초지끼리 연결시켜 주려고 한다.

횡단보도는 도로와 수직일 필요가 없지만, 다른 횡단보도와 겹치면 안되며 각 목초지에 하나의 횡단보도만이 설치되어야 하고, 반드시 친밀한 소들이 위치한 목초지끼리만 연결해줘야한다.

존이 설치할 수 있는 횡단보도의 최대 개수는 몇 개인지 알아보자.