Baekjoon 9527. 1의 개수 세기

9527. 1의 개수 세기

난이도 : 골드 2
소요 시간 : 25분
날짜 : 2024.12.27
언어 : 파이썬
알고리즘 유형 : 수학, 비트마스킹, 누적 합

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. $(x)$는 $x$를 이진수로 표현했을 때에 1의 개수를 의미 한다.
2. $a, b$가 주어지면 $$\sum_{x=a}^{b} f(x)$$ 를 구한다.

2. 해결 방식

1. 음 나는 그냥 재귀함수와 수학으로 풀었는데. 알고리즘 유형은 비트마스킹과 누적 합이라고 한다.
   • 내가 사용한 비트마스킹은 연산을 전혀 사용하지 않고 2 ** index를 left shift를 이용해서 표현한 것 뿐..
2. $c = 2 ^ n$ 일 때, $$\sum_{x=0}^{c} f(x) = \frac{n * c}{2} + 1$$ 이다.
3. 따라서, $x$ 보다 작은 수 중 제일 큰 $2^n$을 찾고
4. 그 다음엔, $x$를 right shift 한 값, 즉 $x - 2 ^ n$의 함수값과 $x - 2 ^ n$값 자체를 더해주면 된다.
   • $2^n$보다 큰 수들만 구해주면 되는데, 이것은 총 $x - 2 ^ n$ 개이며, 각각의 $x - 2 ^ n$개의 수들의 함수값은 $x - 2 ^ n$의 함수값에 1을 더해준 값과 같기 때문이다.

3. 정답 코드

import sys
input = sys.stdin.readline

import math
a, b = map(int, input().split())

def sol(x):
    if x == 0:return 0
    index = int(math.log2(x))
    max_exponential = 1 << index # x 보다 작은 수 중 제일 큰 2**n
    if max_exponential == x:
        return index * x // 2 + 1
    return sol(x - max_exponential) + x - max_exponential + sol(max_exponential)

print(sol(b) - sol(a-1))