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

백준 9527 - 1의 개수 세기

시간 제한 1초, 메모리 제한 128MB

# 조건

• 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.
• 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.

입력

• 첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10^16)

출력

• 1의 개수를 세어 출력한다.

# 접근 방법

• 처음에 어떻게 풀어야 될지 감이 잘 오지 않았던 문제이다.
• 1000조까지의 범위가 주어지므로 무식하게 풀 수 없었기에 규칙을 찾는데 집중하였다.
• 2가지 규칙을 찾을 수 있었는데 우선, 1부터 해당 숫자들을 2진수로 변경 시, 2^n -1 까지의 이진법이 반복되는 패턴이 존재한다.
• 따라서, 다음 2^n 부터 2^(n+1) -1 까지는 2^(n-1) 부터 2^(n) - 1까지의 이진수 패턴에 앞에 1을 붙여준 것과 동일하다.

• 두번쨰는 1의 개수를 누적합으로 구할 경우, 1부터 2^n-1까지의 수를 점화식으로 구할 수 있다.
  • 1 - 1, 2 - 2, 3 - 4, 4 - 5, 5 - 7, 6 - 9, 7 - 12 ....
  • 2 ^ n - 1 의 숫자까지의 1의 개수 누적 합이 2^(n-1) + 2 * (2^(n-1)개 까지의 1의 개수) 라는 것을 도출할 수 있었다.
  • 즉, 15까지 1의 개수는 - 7까지의 1의 누적합 * 2 + (2^4 - 2^3) 과 동일하다.
    • 즉, one_sum[0] = 0
    • one_sum[1] = 2^0 + 2 * 0 = 1
    • one_sum[2] = 2^1 + 2 * 1 = 4
    • one_sum[3] = 2^2 + 2 * 4 = 12
• 2 ^ n - 1 까지의 1의 누적합을 구해주었으니 이제 주어진 구간에서의 합을 구하는 함수를 정의해준다.
  • 우선 구간 x와 y가 주어지면, y까지의 1 count - (x-1)까지의 1 count 이다.
  • 14와 같이 중간의 수가 주어질 수 있기 때문에, 12까지의 1의 개수를 카운팅 해주는 반복문을 구현해준다.
  • 참고 https://yiyj1030.tistory.com/490

[누적합/파이썬] 백준 9527번 : 1의 개수 세기 / 골드 2

 

• 위와 같은 방식으로 반복해주면 된다.

def count(num):  
    cnt = 0  
    bin_num = bin(num)[2:]  
    length = len(bin_num)  
    for i in range(length):  
        if bin_num[i] == '1':  
            # num보다 크지 않으면서 가장 큰 2의 거듭제곱 수  
            val = length-i-1  
            cnt += one_sum[val]  
            # 가장 앞자리 1 개수를 추가로 더해주기  
            cnt += (num - 2**val + 1)  
            num = num - 2 ** val  
    return cnt  

x, y = map(int, input().split())  
one_sum = [0 for _ in range(60)]  

for i in range(1, 60):  
    one_sum[i] = 2**(i-1) + 2 * one_sum[i-1]  

print(count(y) - count(x-1))