[백준17419/실4] 비트가넘쳐흘러 - Python

https://www.acmicpc.net/problem/17419

 

 

 

 

빌런호석(22251번) 풀려고 보니까 비트연산하면 좋을 거 같아서 기본 문제 먼저 풀어봤다.

 

처음에 냅다 while문 돌려서 풀었는데 시간초과났다...

당연함 N 1,000,000이었다

 

조건문 뜯어보니까 이진수 1의 개수 찾는 단순한 코드였다

 

 

문제의 수식 : K - (K & ((~K) + 1))

K = 10110 일 때
1. (~K) = 01001
2. (~K) + 1 = 01010
3. K & ((~K) + 1) = 00010
4. K - (K & ((~K) + 1) = 10100 (가장 오른쪽의 1 사라짐)
-> 이 연산 K가 0이 될 때까지 반복하면 1의 개수만큼 연산 시행

 

 

성공 코드

# K - (K & ((~K) + 1))  # 가장 오른쪽의 1만 삭제
#
# ex. K = 10110
# 1. (~K) = 01001
# 2. (~K) + 1 = 01010
# 3. K & ((~K) + 1) = 00010
# 4. K - (K & ((~K) + 1) = 10100 (가장 오른쪽의 1 사라짐)
#
# -> 이 연산 K가 0이 될 때까지 반복하면 1의 개수만큼 연산 시행


N = int(input())
K = input()
print(K.count("1"))