문제
진홍이는 숫자를 좋아한다. 오늘도 숫자를 가지고 놀던 진홍이는 두 숫자의 비트 우정지수를 구해보았다. 비트 우정지수란, 10진법으로 나타낸 두 정수를 이진수로 나타내었을 때, 두 숫자를 같게 만드는데 필요한 최소 연산 횟수를 말한다. 연산의 종류는 다음과 같다.
- 하나의 이진수에서 임의의 자리의 숫자를 0 또는 1로 바꾼다.
- 하나의 이진수에서 서로 다른 자리에 있는 두 숫자의 위치를 바꾼다.
예를 들어, 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을 넘지 않으며, 자릿수는 서로 같다.
출력
각 테스트 케이스마다 두 수의 비트 우정지수를 출력한다.
예제 입력 1 복사
3
1011 1100
100101 110100
00110100 10010111
예제 출력 1 복사
2
1
3
[소스 코드]
이진수 두 개중에서 하나를 기준으로 잡고 기준과 다른 부분이 몇 번 나오는지 센다.
단 다른 부분이 1인지 0인지를 구분하여 cnt_1과 cnt_0으로 나눠서 세준다.
그래서 두 cnt값중에 큰 값으로 답을 출력한다.
ex)
110100
101011
첫 번째 이진수를 기준으로 했을 때 두 번째 이진수에서 어느 부분이 다른지 확인한다.
idx 0 : 같음
idx 1 : 다름 > cnt_0 증가
idx 2 : 다름 > cnt_1 증가
idx 3 : 다름 > cnt_0 증가
idx 4 : 다름 > cnt_1 증가
idx 5 : 다름 > cnt_1 증가
cnt_0 = 2
cnt_1 = 3
다른 부분은 총 5군데 이지만 여기에서 2군데는 자리 교환으로 같게 만들고, 한 군데는 숫자를 변경해서 같게 만든다.
따라서 3번의 연산으로 같게 만들 수 있다.
import sys
input = sys.stdin.readline
n = int(input())
for _ in range(n):
n, m = input().split()
cnt_1 = 0
cnt_0 = 0
for i in range(len(n)):
if n[i] != m[i]:
if n[i] == '1':
cnt_1 += 1
else:
cnt_0 += 1
print(max(cnt_0,cnt_1))
'알고리즘 > python' 카테고리의 다른 글
[python/파이썬] 백준 13413 오셀로 재배치 (0) | 2022.07.04 |
---|---|
[python/파이썬] 백준 2847 게임을 만든 동준이 (0) | 2022.07.01 |
[python/파이썬] 백준 1817 짐 챙기는 숌 (0) | 2022.06.30 |
[python/파이썬] 백준 16435 스네이크버드 (0) | 2022.06.30 |
[python/파이썬] 백준 11256 사탕 (0) | 2022.06.29 |