존의 고민을 해결할 방법을 찾아 알려 주러 가던 우리는 길을 잃고 말았다. 도착한 곳도 존의 농장이긴 했지만, 목초지 2N개는 없고 웬 N×N 격자가 있었다. 알고 보니 동명이인의 농장이었다. 그 사이에 우리가 도와주려던 존은 자기 코드를 아무리 디버깅해도 틀렸다는 판정이나 런타임 에러가 나자 포기하고 두 번째 방안을 시도하고 있다.
존은 최근에 일부 종끼리 친하다는 사실을 알게 되었다. 존의 농장에는 1번 종, 2번 종, ..., N번 종까지 N 종류의 소가 있다. ∣a−b∣≤4이면 a번 종과 b번 종의 소는 친하고, 그렇지 않으면 사이가 나쁘다.
존 도와주기 협회에 새로 가입한 사람들을 위해 농장의 구조를 다시 설명한다. 농장에는 곧은 길이 하나 있고, 길 양쪽에 목초지가 N개씩 있다. 왼쪽 목초지에는 각 종의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 존은 교통사고를 막으려고 횡단보도를 설치하려 한다. 각 횡단보도는 왼쪽 목초지 하나와 오른쪽 목초지 하나를 이어야 하며, 길에 수직일 필요는 없다. 물론 사이가 좋은 소끼리만 연결해야 한다. 각 목초지에는 횡단보도가 최대 한 개만 있어야 하고, 횡단보도끼리 서로 교차하면 안 된다.
조건을 지키면서 횡단보도를 최대한 많이 설치하도록 존을 도와주자.
cho.sh