[BOJ] 12782 비트 우정지수 바로가기
진홍이는 숫자를 좋아한다. 오늘도 숫자를 가지고 놀던 진홍이는 두 숫자의 비트 우정지수를 구해보았다. 비트 우정지수란, 10진법으로 나타낸 두 정수를 이진수로 나타내었을 때, 두 숫자를 같게 만드는데 필요한 최소 연산 횟수를 말한다. 연산의 종류는 다음과 같다.
예를 들어, 10진수 11과 12의 비트 우정지수를 구해보자. 11을 이진수로 나타내면 1011이고, 12를 이진수로 나타내면 1100이다. 1011에서 2의 자리를 0으로 바꾸고(1011 -> 1001), 1의 자리와 4의 자리의 숫자를 서로 바꾸면(1001 -> 1100) 1100이 된다. 즉, 1011을 1100으로 바꾸는 최소 연산 횟수는 두 번으로, 11과 12의 비트 우정지수는 2가 된다.
진홍이는 어떤 두 수가 주어졌을 때 두 수의 비트 우정지수를 구하는 프로그램을 만들고 싶다. 하지만, 아쉽게도 진홍이는 프로그래밍에 약해 10진수를 이진수로 바꾸는 것 밖에 하지 못한다. 여러분이 진홍이를 도와 두 수의 비트 우정지수를 구하는 프로그램을 만들어 주자!
입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 50)가 주어진다.
각 테스트케이스의 첫 번째 줄에는 두 이진수 N, M이 주어진다. N, M의 자릿수는 1,000,000을 넘지 않으며, 자릿수는 서로 같다.
각 테스트 케이스마다 두 수의 비트 우정지수를 출력한다.
✍ 코드
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
N, M = stdin.readline().split()
ON, OM = N.count('1'), M.count('1') # 비트 지수에 포함된 1의 갯수
count = 0 # 서로 다른 비트의 갯수
for i in range(len(N)):
if N[i] != M[i]:
count+=1
count -= abs(ON-OM)
# 1번 연산 + 2번 연산 + 2번 연산이 끝난 후 남은 비트에 대한 1번 연산
result = abs(ON-OM) + (count%2) + (count//2) #
print(result)