[Python] 백준 9527 1의 개수 세기

 

문제

두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.

즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.

 ∑x=ABf(x)\[\sum_{x=A}^{B}{f(x)}\] 

 

 

 

 

난이도

골드2

 

 

 

 

 

내 코드

import sys

## 1에서 n까지의 1의 갯수 구하는 함수
def hap_1_n(n) : 
    cnt = 0

    x = 1
    nextX = 2
    while True :
        if x > b :
            break

        cnt += (n // nextX) * x
        if (n % nextX) >= x :
            cnt += (n % nextX - x + 1) 

        x = nextX
        nextX *= 2

    return cnt


a, b = map(int,sys.stdin.readline().split())
hap_1_b = hap_1_n(b)
hap_1_a_1 = hap_1_n(a-1)
answer = hap_1_b - hap_1_a_1

print(answer)

 

 

 

풀이과정

이 문제는 구현보다 규칙을 찾는 게 힘들었다.

 

보면 자연수에 따라 규칙적으로 1의 나타남이 반복된다는 것을 알 수 있다.

이 규칙을 보고 내가 생각해낸 방법은

1. 1부터 n까지를 이진수로 만들었을 때 1의 총 갯수를 구하는 함수를 만든다.

2. 함수를 이용해 [1~b] 까지의 1의 합을 구하고, 거기서 [1~(a-1)] 까지의 1의 합을 뺀다.

 

여기서 중요한 점은 1번의 함수를 어떻게 만드냐인데,

나는 

a. 1~n 까지 2^0 이 1인 것의 갯수를 센다.

b. 1~n 까지 2^1 이 1인 것의 갯수를 센다.

c. 1~n 까지 2^2 이 1인 것의 갯수를 센다.

...

이 과정을 반복하여 2의 충분한 승까지의 갯수를 세서 더했다.

그 갯수는 간단한 수식으로 만들수 있는데,

만약 현재가 2^x 의 1의 갯수를 계산하고 있다고 하면 1의 갯수는

n // 2^(x+1) * 2^x

이것이고 만약 n % 2^(x+1) 의 나머지가 2^x 보다 같거나 크다면 여기다 n % 2^(x+1) - 2^x + 1 을 더해주면 된다.

 

이건 2의 2승은 2의 3승의 주기로 반복하고, 2의 3승은 2의 4승의 주기로 반복하는 특징을 찾아 발견한 방법이다..

이렇게 바로 1의 갯수가 나오게 식을 생각하는 과정이 오래 걸려 힘든 문제였다....