구간 내 가장 큰 해밍거리를 가지는 두 정수를 구하는 방법

33692번: 해밍 거리

 

두 정수 a,b의 해밍거리는 a,b를 각각 이진수로 나타내서, 동일한 위치의 비트를 비교하여 서로 다른 비트의 수를 말한다.

 

예를 들어

 

9 = 1001

 

12 = 1100이므로, 2번째 비트와 4번째 비트가 서로 달라 9,12의 해밍거리는 2이다.

 

두 정수 A,B가 주어질때 A이상 B이하에서 해밍거리가 가장 큰 두 정수 a,b를 아무거나 구한다.

 

--------------------------------------------------------------------------------------------------------------------------------------------------------

 

A,B를 각각 이진수로 나타내고 이진수의 길이가 서로 다르다면, 앞에 0을 채워넣어서 두 이진수의 길이를 맞춰준다

 

당연히 B가 더 크니까, 더 길어서 A 앞에 0을 채워준다

 

이제 두 이진수를 상위비트부터, 차례대로 비교해나간다.

 

그러다가 비트가 서로 다른 지점이 발생한다면, 

 

A = 1111111....110XXXXXXXXXX...

B = 1111111....111YYYYYYYYYY...

 

반드시 위와 같이 될 것이다. 왜냐하면 A보다 B가 더 크기 때문이다. 

 

그러면 

 

A에서는 0 이후로 모두 1로 채우고, B는 1이후로 모두 0을 채우면 그것이 해밍거리가 최대가 된다

 

X = 1111111....1101111111111111...

Y = 1111111....111000000000000...

 

이렇게하면, X는 A이상이 되는데 B를 넘지 못하고, Y는 B 이하가 되는데 A보다 반드시 크거나 같다는것도 주목할만하다

 

 

a,b = map(int,input().split())

a = bin(a)[2:]
b = bin(b)[2:]

a = '0'*(len(b) - len(a)) + a

X = []
Y = []

for i in range(len(a)):
    
    if a[i] != b[i]:
        
        X.append('1')
        Y.append('0')
        break
    
    else:
        
        X.append(a[i])
        Y.append(a[i])

X = ''.join(X)
Y = ''.join(Y)

X += '0'*(len(a)-1-i)
Y += '1'*(len(a)-1-i)

print(int(X,2),int(Y,2))