백준 12782

문제 링크
난이도 : 실버5

풀이

해당 문제에서의 연산은 두 가지입니다.

1. 0을 1로, 1을 0으로 바꾸거나
2. 다른 자리의 수끼리 위치를 바꾸는 것 (0<->1 swap 연산)

그러므로 만약 입력되는 첫 번째 이진수를 origin, 두 번째 이진수를 dest로 origin에서 dest로 바꾸는 것을 목적으로 하고, 최소한의 연산으로 바꾼다고 가정하였을 때, origin과 dest가 차이가 나는 파트는 두 가지 경우입니다.

1. origin bit가 0에서 dest bit 1로 바뀜
2. origin bit가 1에서 dest bit 0으로 바뀜
   두 가지 경우밖에 없으므로, 만약 0에서 1로 바뀌는 횟수가 N1, 1에서 0으로 바뀌는 횟수가 N0이라 생각해보면, SWAP으로 해결 가능한 부분(abs(N1-N0))은 해결한 후, 그래도 바뀌지 않았다면 비트를 바꿔주면 되겠습니다. 이때 비트를 바꿔주는 건 N0, N1 중에 작은 수(min(N1,N0))입니다. 왜냐하면 더 큰 수와 작은 수의 차이 만큼 이미 SWAP으로 바꿨기 때문입니다.

주의할 점은 시간 제한은 1초이며, 최대 50개의 테스트 케이스, 최대 1,000,000(10^6)만큼의 N이 입력됩니다. 10^8의 연산량이 1초 가량 걸리기 때문에, 단 한 번만에 반드시 비교를 끝내주셔야 합니다. 아래의 코드는 for loop 1회만 착실하게 순회하는 O(N)으로 시간 제한 내에 반드시 통과하게 됩니다.

코드

T = int(input())
for _ in range(T) :
  a, b = input().split()
  N0 = 0
  N1 = 0
  for i in range(len(a)) :
    if(a[i] != b[i] and b[i] == '1') :
      N1 += 1
    elif (a[i] != b[i] and b[i] == '0') :
      N0 += 1
  print(min(N1,N0)+abs(N1-N0))