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

존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다.

각각 1번 종, 2번 종, ..., N번 종이다.

만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다.

농장에는 일자형 길이 있고, 해당 길을 기준으로 양쪽에 목초지가 N개씩 있다.

왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다.

교통사고를 막기 위해 존은 횡단보도를 설치하려고 한다.

각 횡단보도는 왼쪽과 오른쪽에 있는 목초지를 하나씩 이어야 하고, 길이 수평일 필요는 없다.

물론 사이가 좋은 소들끼리 연결해야 한다.

각 목초지에는 최대 한 개의 횡단보도만 있어야 한다.

그리고 횡단보도가 겹치면 안 된다.

존이 설치 할 수 있는 가능한 한 많은 횡단보도의 수는 얼마인지 알아보자.