폴리매스

어떤 나라의 항공노선은 어떤 두 도시를 직항으로 왕복하는 노선으로 구성되어 있다. 임의의 도시에서 다른 도시로 여러 항공편을 갈아타고 갈 수 있었으며, 두 도시의 ‘거리’를 한 도시에서 다른 도시로 항공편으로 이동할 때 필요한 항공편 탑승 회수의 최솟값이라고 하자. 임의의 도시에서 정확히 거리 3 떨어진 도시의 수가 n개 이하였다고 한다. 이때 거리가 정확히 4 떨어진 도시를 k개보다 많이 가진 도시는 존재하지 않았다고 한다. k의 최솟값을 n으로 나타내어라.