[백준 17419] 비트가 넘쳐흘러 Python

17419번 - 비트가 넘쳐흘러

문제 이해

N자리 이진수 K가 주어지면, K가 0이 될 때 까지
K = K-(K&((~K)+1)) 연산을 반복하며 반복이 일어나는 횟수 구하기

접근

Naive한 방법

N = input()
K = int(input(), 2) # 2진수
cnt = 0
while K:
  K = K-(K&((~K)+1))
  cnt += 1
print(cnt)

문제의 설명을 그대로 따라 한 방법으로, 제출 시 51점을 맞게 된다.

생각

식을 정리해볼 수 있을까? 하는 생각에 시도해 보았지만, 산술연산과 비트연산이 함께 있어 이상의 정리는 힘들었다.

식을 한단계씩 적용시켜보며 규칙을 살펴보았다.
문제에서 예시로 준 K = 10110을 살펴보면

• 10100
• 10000
• 00000

이 됨을 알 수 있었고, 오른쪽부터 1이 하나씩 0으로 바뀐다.
식을 보면, ~K를 통해 모든 비트를 반전시키고, +1을 하게 되면 오른쪽 끝의 연속된 1들이 0으로 바뀌며, 연속이 끝나는 부분의 0이 1이 된다.
반전되었던 비트였으므로, 해당 부분은 기존 K의 가장 오른쪽에 있던 1이 된다.
&연산을 하게 되면 두 비트 모두 1인, 기존 K의 가장 오른쪽에 있던 1의 자리만 1이고 나머지 비트는 0이 되며, 이를 기존 K에서 빼주면 결과적으로 기존 K의 가장 오른쪽에 있던 1이 0으로 바뀌는 것이다.

따라서 해당 문제는 다음의 문제로 바뀐다.

주어진 N자리 이진수 K의 1의 개수를 출력하라

1의 개수를 세는 문제이기에 굳이 이진수로 입력받고 처리 할 필요가 없으며, 문자열로 입력을 받고, 파이썬의 문자열 메서드 count를 사용해 해결했다.

정답 코드

input() # N을 사용할 필요가 없어 굳이 변수에 담지 않았다.
print(input().count('1'))