알고리즘 - Python / 백준 - 9527번 : 1의 개수 세기

9527번: 1의 개수 세기 (acmicpc.net)

9527번: 1의 개수 세기

 

---

풀이

• 어떤 범위 안의 모든 이진수들의 1의 개수를 더해 출력하면 되는 문제다.
• 최대 범위가 10^16 이므로 단순하게 모두 세는 방법으로는 어렵다고 판단했다.
• 이진수의 특징 중 하나가 점점 수가 커짐에 따라 다음 자릿수에 1 혹은 0이 오므로 부분 문제를 전체 문제에 사용할 수 있다고 판단하고 , 이를 이용하기로 했다.
• 또한 어떠한 범위 내의 수를 구하는 문제이므로 누적합을 사용하기로 했다.
• 이진수의 특징과 누적합 과정을 통해서 확인한 결과 , N자리 수까지의 1의 개수 누적합은 이전 경우 * 2 + 2^(N-1)이다.
• 누적합 구한 이후에는 다음 그림과 같이 풀이를 진행하였다.
• 그림에는 나와있지 않지만 , 코드에서는 경곗값에 1이 포함되는 경우를 예외 처리하여 답을 냈다.

 

 

 

 

 

 

 

import sys
n ,m= map(int,sys.stdin.readline().split(" "))
dp = [1]
for i in range(1,55):
    dp.append(2*dp[i-1] + 2**i)

def smaller(num):
    ans = 0
    bits = bin(num).replace("0b","")
    ans = int("0b" + bits[1:len(bits)], 2)
    for i in range(1,len(bits)-1):
        if bits[i] == "1":
            ans += (smaller(int("0b" + bits[i:len(bits)],2)) + dp[len(bits)-i-2])
            break
    return ans

if n == 1:
    if m == 1:
        space = 1
    else:
        space = dp[(len(bin(m).replace("0b",""))-2)] + smaller(m)+ bin(m).count("1")
else:
    space = dp[(len(bin(m).replace("0b",""))-2)] - dp[(len(bin(n).replace("0b",""))-2)]
    space = space + smaller(m) - smaller(n) + bin(m).count("1")
print(space)

---