CIDR

인터넷 프로토콜(IP) V4 주소는 인터넷에서 호스트를 유일하게 식별하는 32비트 정수다. IP 주소는 192.168.1.100처럼 점으로 구분한 네 부분 형식으로 쓴다. 각 부분은 8비트 부호 없는 값을 나타내며, 32비트 정수 주소의 4바이트에 각각 대응한다. IP 주소는 이 32비트 정수 안에서 두 비트 묶음을 정한다. 네트워크 부분과 호스트 부분이다. 주소의 하위 비트는 상위 비트가 나타내는 네트워크 안의 특정 호스트를 가리킨다.

네트워크 마스크는 네트워크 부분의 모든 비트를 1로 설정한 비트마스크다. 예를 들어 네트워크 부분이 14비트이면 넷마스크는 0xfffc0000이고, 점 형식으로는 255.252.0.0이다.

역사적으로 각 부분은 8, 16, 24처럼 8비트의 배수로 이루어졌다. 그래서 IP 주소 할당에 문제가 생겼다. 네트워크 개수가 대부분의 조직이 쓰기에는 너무 많거나 너무 적었다. 네트워크 하나의 최소 호스트 수는 256개(호스트 부분 8비트)였다. 작은 네트워크가 256개의 호스트를 필요로 하는 경우는 드물었기 때문에, 이는 IP 주소 공간의 낭비로 이어졌다.

이 문제를 해결하려고 CIDR(Classless Inter-Domain Routing)이 도입되었다. 네트워크 부분과 호스트 부분에 쓰는 비트 수는 두 부분의 합이 32이기만 하면 어떤 수든 쓸 수 있다. CIDR 표기는 점으로 구분한 IP 주소, 슬래시(/) 문자, 10진수(0-32)로 이루어진다. 예를 들어 192.168.1.100/14는 IP 주소 192.168.1.100과 그에 대응하는 네트워크 프리픽스 192.128.0.0을 나타낸다. 이는 넷마스크 255.252.0.0과 같으며, 앞에서부터 1이 14개 있다.

이 문제에서는 점으로 구분한 IPv4 주소 목록을 입력받아, 지정된 모든 IP 주소를 포함하면서 사용되지 않거나 낭비되는 호스트 수가 가장 적은 네트워크 부분을 구하는 프로그램을 작성한다.

입력의 첫 줄에는 뒤따르는 점으로 구분한 IP 주소의 개수 N (2 ≤ N ≤ 65535)이 10진수 정수로 주어진다. 이어서 N줄에 각각 유효한 점 형식 IP 주소가 한 개씩 주어진다.

출력은 한 줄이며, 네트워크 부분의 비트 수를 나타내는 정수 하나다. 즉 네트워크 부분에 속한 주소의 CIDR 표기에서 슬래시(/) 뒤에 오는 정수 값이다. 주어진 IP 주소들이 공통으로 가지는 네트워크 부분이 없으면 32를 출력한다. 이는 특정 호스트를 가리킬 때 흔히 쓰는 특별한 경우로, 네트워크 부분이 없다는 뜻이다. 따라서 0을 출력하는 경우는 없다.