[2064] IP 주소

https://www.acmicpc.net/problem/2064

기본적으로 네트워크 이론이 좀 필요한 문제입니다.

서브넷 마스크 & ip 주소 = 네트워크 주소

라는 것을 알아야하며..

가장 크기가 작은(포함되는 IP 주소가 가장 적은, 즉 m이 최소인) 네트워크를 구하도록 한다.

라는 조건이 중요합니다.

모든 ip에 대해서 공통된 부분을 찾습니다.

모든 ip에 대해서 공통된 부분(왼쪽 비트 부터 시작해서 오른쪽 비트로 갈 때)

만약 다른 부분이 있으면 멈춰야합니다.

ip에서 네트워크 주소나 서브넷을 따질 때

nnnn.nnnn.nnnn.nnhh

이런식으로 n은 이어져야합니다.(n은 네트워크 h는 호스트)

무튼... 기본 이론은 이러합니당..

공통된 부분은 전부 1로 가득채워서 서브넷 마스크를 구하면

서브넷 마스크 & 임의의 ip주소 = 네트워크 주소 를 출력할 수 있습니다.

코드입니다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int ip[1000];
 
void print(int mask) {
    int shift = 24;
    for (int i = 0; i < 4; i++, shift -= 8) {
        cout << ((mask >> shift) & (1 << 8) - 1);
        if (i != 3) cout << '.';
    }
    cout << '\n';
}
 
int main() {
    int n;
    cin >> n;
 
    //ip입력받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            int a;
            cin >> a;
            ip[i] <<= 8;
            ip[i] |= a;
            getchar();
        }
    }
 
    //서브넷
    int subnet = 0;
 
    //0번째 ip와 틀린부분 찾기
    //찾으면 탈출해서 틀린부분 전까지는 전부 1로 채우기.
    for (int i = 31; i >= 0; i--) {
        int bit = 1 << i;
        bool end = 0;
 
        for (int j = 1; j < n; j++) {
            if ((ip[0] & bit) != (ip[j] & bit)) {
                end = 1;
                break;
            }
        }
 
        if (end) break;
        else subnet |= bit;
    }
 
    //네트워크 주소 출력하기
    print(ip[0] & subnet);
    //서브넷 주소 출력하기
    print(subnet);
 
    return 0;
}