[백준 파이썬] 9527 1의 개수 세기

백준 9527

https://degurii.tistory.com/158
정리가 굉장히 잘 되있다. 이 글을 보고도 헷갈렸던 부분만 정리하면

처음 i 번째(i=3이라면 1000부터 1111까지) 자리까지 모두 더해주는 값은, 가장 높은 자리의 수 = $2^i$와 그 이하 자리에 있는 수의 합이다. 이전 자리의 수를 보면 그 앞자리, 아래 사진에서는 i=2 일 때, 모든 수와 동일해 두 번 더해주는 값이 된다. 그래서 i 번째 자리까지는

2 * dp[i-1] + 1 << i

가 된다.
다음으로 자리수까지 모든 합이 아닌 그 사이에 있는 값을 가져와야 하는 경우에는 i-1 번째 자리까지 모든 자리수까지 합 + i-1 번째 자리의 1의 개수 를 반복해서 더해주면 된다.

예를 들어 $14 = 1101_{(2)}$를 계산한다면

처럼 반복문으로 풀어 줄 수 있다.

max_len = len(bin(10**16)[2:])
dp = [0 for _ in range(max_len)]
dp[0] = 1
for i in range(max_len):
    dp[i] = 2 * dp[i-1] + (1<<i) # 초기값, i 번째 자리수까지 1의 합

def suffix_sum(x):
    ans = x & 1 # 0 번째 자리 수
    for i in range(max_len, 0, -1): # 가장 높은 자리 수 부터 
        if x & 1 << i: # x가 i 번째 자리에 값을 가지고 있다면
            ans += dp[i-1] + x - (1<<i) + 1 # 1의 수 계산
            x -= 1<<i # 가장 높은 자리의 1의 수는 계산 되었으므로 제거
    return ans

A, B = map(int, input().split())
print(suffix_sum(B) - suffix_sum(A-1))